Здравствуйте!

Писал-писал программку. Бац, наткнулся на задачу перебора. И что-то как-то колом встала. Возможно все очень просто, но что-то не пошло.
Вообщем, задача такая.

1,2,3,4,5 это исходная последовательность. N = 5. Нужно перебрать по M-элементам, пусть M=3, т.е. хочется получить что то следующего вида

123
124
125
134
135
...
543

Желательно не рекурсивное решение. В моей конкретной задаче 3<N<=400, 3<M<15
Хочу организовать с помощью метода MoveNext() например. т.е. приветствуется вычисление новой последовательности на каждом шаге.

С нетерпением жду ответов.

С уважением, Иван.

Здравствуйте, WSN, Вы писали:

WSN>С нетерпением жду ответов.

Возможно вам поможет код функции permutations из питона — http://docs.python.org/library/itertools.html

WSN>С нетерпением жду ответов.

код на шелле:

move_next() (
  if test $# -lt 2; then
    echo
    exit 1
  fi
  BOUND=$1
  shift
  FIRST=$1
  shift
  if test $FIRST -ge $(($BOUND - $#)); then
    exit 1
  fi
  if NEXT=$(move_next $BOUND $@); then
    echo $FIRST $NEXT
  else
    { seq $(($FIRST + 1)) $(($FIRST + 1 + $#)) | tr \\n ' '; echo; }
  fi
)

пример использования:

$ move_next 5 1 2 5
1 3 4

WSN>Желательно не рекурсивное решение. В моей конкретной задаче 3<N<=400, 3<M<15

$ time move_next 400 4 5 7 9 43 50 66 89 91 92 145 234 237 290 345 396 397 398 399 400
4 5 7 9 43 50 66 89 91 92 145 234 237 290 346 347 348 349 350 351

real 0m0.037s
user 0m0.010s
sys 0m0.030s

генерация всех комбинаций:

$ NEXT="1 2 3"; while NEXT=$(echo $NEXT 1>&2; move_next 5 $NEXT); do true; done
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

Здравствуйте, WSN, Вы писали:

WSN>1,2,3,4,5 это исходная последовательность. N = 5. Нужно перебрать по M-элементам, пусть M=3, т.е. хочется получить что то следующего вида

WSN>123
WSN>124
WSN>125
WSN>134
WSN>135
WSN>...
WSN>543
WSN>
WSN>В моей конкретной задаче 3<N<=400, 3<M<15

Хм, немного странным выглядит финальный кортеж "543" (точнее, даже не он сам, а порядок элементов в нём).
Судя по началу, речь идёт о сочетаниях:
123
124
125
134
135
145
234
235
245
345

Кстати, их число определяется известной формулой: n! / (k! * (n-k)!), что для ваших значений (N=400, M=15) даёт число вариантов примерно 2^90, поэтому полный перебор может несколько затянуться

WSN>В моей конкретной задаче 3<N<=400, 3<M<15
A>Кстати, их число определяется известной формулой: n! / (k! * (n-k)!), что для ваших значений (N=400, M=15) даёт число вариантов примерно 2^90, поэтому полный перебор может несколько затянуться

но у него не сказано что M и N обязательно достигают максимума одновременно

Здравствуйте, dilmah, Вы писали:


WSN>>С нетерпением жду ответов.

D>код на шелле:

D>

D>move_next() (
D>  if test $# -lt 2; then
D>    echo
D>    exit 1
D>  fi
D>  BOUND=$1
D>  shift
D>  FIRST=$1
D>  shift
D>  if test $FIRST -ge $(($BOUND - $#)); then
D>    exit 1
D>  fi
D>  if NEXT=$(move_next $BOUND $@); then
D>    echo $FIRST $NEXT
D>  else
D>    { seq $(($FIRST + 1)) $(($FIRST + 1 + $#)) | tr \\n ' '; echo; }
D>  fi
D>)
D>

D>пример использования:

D>

D>$ move_next 5 1 2 5
D>1 3 4
D>

К сожалению, не понял, а в 2х словах в чем суть?
У меня 1,2,3,4,5 заданы в виде массива
var scope = new int[]{1,2,4,5};
ну и на каждом MoveNext хотелось бы чтото вроде того же массива из предположим 3х элементов
var iter = new int[3]
Ну а при каждом MoveNext чтоб значения массива iter обновлялись.

Здравствуйте, andy1618, Вы писали:

A>Здравствуйте, WSN, Вы писали:

WSN>>1,2,3,4,5 это исходная последовательность. N = 5. Нужно перебрать по M-элементам, пусть M=3, т.е. хочется получить что то следующего вида

WSN>>123
WSN>>124
WSN>>125
WSN>>134
WSN>>135
WSN>>...
WSN>>543
WSN>>
WSN>>В моей конкретной задаче 3<N<=400, 3<M<15

A>Хм, немного странным выглядит финальный кортеж "543" (точнее, даже не он сам, а порядок элементов в нём).
A>Судя по началу, речь идёт о сочетаниях:
A>123
A>124
A>125
A>134
A>135
A>145
A>234
A>235
A>245
A>345

A>Кстати, их число определяется известной формулой: n! / (k! * (n-k)!), что для ваших значений (N=400, M=15) даёт число вариантов примерно 2^90, поэтому полный перебор может несколько затянуться

Да, интересуют имеенно сочетания.
Согласен, что это тяжелая задача, но у меня к сожалению только полный перебор возможен. Это из радела графов, там надо искать все вхождения подграфа в граф, почитал массу статей, везде пишут, что полный перебор только((

WSN>К сожалению, не понял, а в 2х словах в чем суть?
WSN>У меня 1,2,3,4,5 заданы в виде массива

у функции move_next первый аргумент -- это N (в твоей терминологии). Остальные аргументы -- это текущая комбинация. Функция печатает следующую комбинацию.

К сожалению или к счастью в стандартном шелле нет массивов..

Здравствуйте, dilmah, Вы писали:


WSN>>К сожалению, не понял, а в 2х словах в чем суть?
WSN>>У меня 1,2,3,4,5 заданы в виде массива

D>у функции move_next первый аргумент -- это N (в твоей терминологии). Остальные аргументы -- это текущая комбинация. Функция печатает следующую комбинацию.

D>К сожалению или к счастью в стандартном шелле нет массивов..

Ну тогда для моей задачи все равно не понятно, почему

$ move_next 5 1 2 5

А не

$ move_next 3 1 2 3 4 5

?

ЗЫЖ Честно, не знаком с этим шеллом совсем, хотелось бы понять суть, ну хоть на псевдоязыке, например
Выставляем тото в тото
Если тото, делем тото, в противном случае тудато. Ну как то так.

Возможно задача в другом и я просто несколько напутал в понятиях.
Нужны сочетания из M по N, т.е. всего N элементов, а надо сделать сочетания по M Элементов.

WSN>Ну тогда для моей задачи все равно не понятно, почему

WSN>$ move_next 5 1 2 5

WSN>А не

WSN>$ move_next 3 1 2 3 4 5

потому что я считаю, что N=5 неявно задает нам множество тех объектов которыми мы оперируем (делаем выборки).

Здравствуйте, WSN, Вы писали:

WSN>1,2,3,4,5 это исходная последовательность. N = 5. Нужно перебрать по M-элементам, пусть M=3, т.е. хочется получить что то следующего вида

WSN>123
WSN>124
WSN>125
WSN>134
WSN>135
WSN>...
WSN>543

Ну вот такое решение есть для статически заданных констант

int M = 3;
int N = 5;
int[] arr = new int[]{1,2,3,4,5}
for (var i = 0; i<N;i++)
for (var j = 0; j<N;j++)
for (var k = 0; k<N;k++)
{
  if (i == j || j == k || i == k) continue;
  a2[1] = arr[i];
  a2[2] = arr[j];
  a2[3] = arr[k];
  CallbackChnaged(a2);
}

Но хотелось бы как-то это сделать универсально для любых M и N

Здравствуйте, dilmah, Вы писали:


WSN>>Ну тогда для моей задачи все равно не понятно, почему

WSN>>$ move_next 5 1 2 5

WSN>>А не

WSN>>$ move_next 3 1 2 3 4 5

D>потому что я считаю, что N=5 неявно задает нам множество тех объектов которыми мы оперируем (делаем выборки).

т.е. N = 5 подразумевает последоватьельность 1 2 3 4 5, ну тогда зачем же $ move_next 5 1 2 5 ?

WSN>т.е. N = 5 подразумевает последоватьельность 1 2 3 4 5, ну тогда зачем же $ move_next 5 1 2 5 ?

ну ты же сам написал, что хочешь что-то в стиле move_next -- то есть не сразу сгенерировать все комбинации, а иметь функцию которая генерирует "следующую" комбинацию. Для того чтобы сгенерировать следующую комбинацию нужно указать текущую комбинацию. Мне кажется это логично

Здравствуйте, WSN, Вы писали:

WSN>1,2,3,4,5 это исходная последовательность. N = 5. Нужно перебрать по M-элементам, пусть M=3, т.е. хочется получить что то следующего вида
WSN>Желательно не рекурсивное решение. В моей конкретной задаче 3<N<=400, 3<M<15
WSN>Хочу организовать с помощью метода MoveNext() например. т.е. приветствуется вычисление новой последовательности на каждом шаге.

Алгоритмы могут иметь следующие особенности:
1 Определенный порядок перебора: обычно лексикографический порядок, т.е. последовательности идут в таком порядке, в каком они были бы в словаре.
2 "Близость" последовательных сочетаний, т.е. сколько элементов надо изменить, чтобы получить новую последовательность из предыдущей: тут обычно ищут алгоритм, при котором на каждом шаге изменяется только один элемент (иногда изменение элементов последовательности -- дорогая операция).
3 Сохранение позиции каждого элемента, кроме изменяемых на данном шаге (без "перескоков"), т.е., например, 013->023 удовлетворяет этому требованию, 013->034 -- нет (в обоих случаях меняется только один элемент, но во втором для изменения надо еще сдвинуть 3 на вторую позицию). Если массив меняется на месте, то перескок элементов становится дорогим.
4 Генерация новой последовательности на основании предыдущей (next): некоторые алгоритмы реализуются только в цикле, т.к. генерация последовательностей требует дополнительной информации, next-реализации используют только текущую последовательность для генерации следующей.
5 Цикличность: применение того же алгоритма next к последней последовательности должно давать изначальную. Для 1 это не так, т.е. надо либо сигнализировать о том, что на вход поступила последняя последовательность, либо организовать цикличность вручную. Для 4 бывает, что тот же алгоритм автоматически превращает последнюю в первую, но не всегда. А вот для алгоритмов 2 и 3 это может оказаться существенным. Если последняя генерируемая последовательность сильно отличается от первой, то ее уже вручную "за один шаг" не поменяешь, т.е. если цикличность сильна нужна, надо искать другие алгоритмы (если они вообще есть).

Ни один алгоритм не будет удовлетворять всем пунктам сразу. Тебе, судя по MoveNext, надо пункт 4. Самый простой алгоритм, удовлетворяющий 1, 4 и 5, такой (написать такой алгоритм достаточно просто, надо просто задать самому себе вопрос, а что я стал бы делать, если бы увидел последовательность и захотел выписать следующую, которая идет за этой в словаре):

// на вход подается текущая последовательность x длины m с элементами из 1..n, которая меняется "на месте"
next (x: array) {
  if (x[0] > n-m) x = [ 1, 2, ..., m ]; return; // тут мы делаем цикличность вручную: если я увидел "эюя", то словарь закончился
  if (x[m-1] < n) ++x[m-1]; return; // если последний элемент не максимальный, просто увеличиваем его: после "вал" должно идти "вам"
  // теперь мы знаем, что x[0] <= n-m и x[m-1] >= n, т.е. разница между ними >= m,
  // и где-то есть пара последовательных элементов с разницей >= 2, нам нужна такая последняя пара:
  j = m-2;
  while (x[j] + 1 >= x[j+1]) --j;
  // x[j] увеличиваем на один, за ним выстраиваем все по порядку: после "имя" идет "ино"
  s = ++x[j];
  x = [ x[0], ..., x[j], s+1, s+2, ..., s+m-1-j ];
}

Алгоритмы для 2 и 3 обычно базируются на рекурсивных соотношениях, т.е., как правило, не удовлетворяют 4 (и уж точно не удовлетворяют 1). Пусть P(a..b, m) -- такой алгоритм для всех выборок длины m из диапазона a..b, причем первая a(a+1)..., последняя ...(b-1)b. Например, P(1..5, 3) от 123 до 345. А R(a..b, m) -- этот же алгоритм, но наоборот от ...(b-1)b до a(a+1).... Тогда можно сделать рекурсию по двум цифрам (по одной не выйдет, т.к. нарушится условие от 12..m до (n-m+1)..(n-1)n):

// выборки m элементов из 1..n, первая 1..m, последняя (n-m+1)..n
P(1..n, m) =
   1 2 P(3..n, m-2) // есть 1 и 2: от 123..m до 12(n-m+3)..n
   1 R(3..n, m-1)   // есть только 1: от 1(n-m+2)..n до 134..(m+1)
   P(2..n, m)       // нет 1: от 234..(m+1) до (n-m+1)..n
// выборки m элементов из 1..n, первая (n-m+1)..n, последняя 1..m
R(1..n, m) =
   R(2..n, m)       // нет 1: от (n-m+1)..n до 234..(m+1)
   1 P(3..n, m-1)   // есть только 1: от 134..(m+1) до 1(n-m+2)..n
   1 2 R(3..n, m-2) // есть 1 и 2: от 12(n-m+3)..n до 123..m

Здравствуйте, dilmah, Вы писали:


WSN>>т.е. N = 5 подразумевает последоватьельность 1 2 3 4 5, ну тогда зачем же $ move_next 5 1 2 5 ?

D>ну ты же сам написал, что хочешь что-то в стиле move_next -- то есть не сразу сгенерировать все комбинации, а иметь функцию которая генерирует "следующую" комбинацию. Для того чтобы сгенерировать следующую комбинацию нужно указать текущую комбинацию. Мне кажется это логично

логично, спасибо.. т.е. получается можно написать такую функцию, для которой на входе достаточна текущая комбинация и общее количество элементов.

Здравствуйте, WSN, Вы писали:

WSN>

WSN>int M = 3;
WSN>int N = 5;
WSN>int[] arr = new int[]{1,2,3,4,5}
WSN>for (var i = 0; i<N;i++)
WSN>for (var j = 0; j<N;j++)
WSN>for (var k = 0; k<N;k++)
WSN>{
WSN>  if (i == j || j == k || i == k) continue;
WSN>  a2[1] = arr[i];
WSN>  a2[2] = arr[j];
WSN>  a2[3] = arr[k];
WSN>  CallbackChnaged(a2);
WSN>}

WSN>

WSN>Но хотелось бы как-то это сделать универсально для любых M и N

Тут ты генеришь не сочетания, а все перестановки, которых в M! раз больше.

может не самое оптимальное, но работает:

perm _ 0 = []
perm l 1 = [[e] | e <- l]
perm l m = concat [(map (e:) rest) | e <- l, rest <- [(perm (delete e l) (m-1))]]

Здравствуйте, WSN, Вы писали:

WSN>1,2,3,4,5 это исходная последовательность. N = 5. Нужно перебрать по M-элементам, пусть M=3, т.е. хочется получить что то следующего вида

WSN>123
WSN>124
WSN>125
WSN>134
WSN>135
WSN>...
WSN>543

WSN>Желательно не рекурсивное решение. В моей конкретной задаче 3<N<=400, 3<M<15
WSN>Хочу организовать с помощью метода MoveNext() например. т.е. приветствуется вычисление новой последовательности на каждом шаге.

Ну и размещай их постепенно увеличивая в лексикографическом порядке, что может быть проще. Собственно, ты их так сейчас и размещаешь. Или не можешь понять как по текущему размещению сгенерировать следующее?

Все просто. Сначала пытаемся увеличить на единицу крайний справа регистр текущего размещения. Смотрим, что у нас туда записано, берем следующий по возрастанию элемент в исходной последовательности, проверяем, не используется ли он уже в других регистрах нашего размещения, и если не используется — записываем его в крайний справа регистр. Если используется — берем следующий по возрастанию в исходном массиве (исходный массив изначально должен быть упорядочен по возрастанию!!!), проверяем его, и так далее. Если все кандидаты для крайнего справа закончились, переходим к предпоследнему регистру текущего размещения, пытаемся его увеличить таким же способом. После того, как в предпоследний что-то записали, в последний регистр записываем минимальный из оставшихся возможных. Если и с предпоследним нас постигла неудача, двигаемся еще глубже влево вплоть до первого регистра. Как только в какой-то из регистров удалось записать, в ближайший правый от него записываем минимальный из оставшихся возможных, в тот, что еще правее — минимальный из остальных оставшихся, и так далее, все в соответствии с лексикографическим порядком.

Понимаю, что объяснение возможно, путанное, но если посмотреть внимательно, как ты их выписываешь руками, то алгоритм становится просто очевидным. Реализация возможно, потребует некоторых усилий, структуры данных там правильно оформить и в циклах не запутаться, какую-то оптимизацию возможно провести может понадобиться, но идея видится в общем-то довольно очевидной