Алгоритм перестановки элементов в массиве

Рассмотрим следующий сценарий.

У меня есть массив чисел:

 [ 1,2,3,4 ]

Если бы этот массив был объединен, у меня был бы номер 1234.

Я хочу поменять местами числа, чтобы получить самое близкое большее число.

1234 станет 1243, которое станет 1324, которое станет 1342 и т. д.

Какой алгоритм мне нужно использовать, чтобы внести эти изменения в массив?

В идеале я хотел бы использовать алгоритм таким образом: (скажем, у Array есть этот алгоритм как функция, называемая пошаговым руководством)

 [ 1,2,3,4].walkthrough() # gives [ 1, 2, 4, 3 ]
 [ 1,2,4,3].walkthrough() # gives [ 1, 3, 2, 4 ]

список номеров продолжается:

1234
1243
1324
1342
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241


arrays algorithm permutation
person Stefan    schedule 27.08.2009    source источник
comment
Пожалуйста, продолжайте числовую строку. После 1342 года, я полагаю, наступит 1432 год, а что потом? 4132, а затем 4312, а затем 4321?   -  person Lasse V. Karlsen    schedule 27.08.2009
comment
Я думаю, что в вашем списке ошибка, разве 2413 не должны следовать за 2341?   -  person AShelly    schedule 27.08.2009
comment
да ... спасибо ... это было исправлено   -  person Stefan    schedule 28.08.2009

Ответы (2)


arrow_upward
9
arrow_downward

Это дает вам следующую перестановку:

bool Increase(int[] values) {
   // locate the last item which is smaller than the following item
   int pos = values.Length - 2;
   while (pos >= 0 && values[pos] > values[pos + 1]) pos--;
   // if not found we are done
   if (pos == -1) return false;
   // locate the item next higher in value
   int pos2 = values.Length - 1;
   while (values[pos2] < values[pos]) pos2--;
   // put the higher value in that position
   int temp = values[pos];
   values[pos] = values[pos2];
   values[pos2] = temp;
   // reverse the values to the right
   Array.Reverse(values, pos + 1, values.Length - pos - 1);
   return true;
}

Изменить:
Изменен Array.Sort в Array.Reverse. Элементы всегда располагаются в порядке убывания и должны быть в порядке возрастания, чтобы они давали одинаковый результат.

person Guffa    schedule 27.08.2009
comment
у вас есть Ruby-эквивалент этой части Array.Sort? - person Stefan; 28.08.2009
comment
@Stefan: Я никогда не использовал Ruby, поэтому нет. Эта перегрузка метода Array.Sort сортирует часть массива, начиная с индекса во втором аргументе и длины в третьем аргументе. - person Guffa; 28.08.2009
comment
@paracycle: Спасибо. Да, это C #. Я это только что придумал, а может, и заново ... :) - person Guffa; 28.08.2009
comment
Если подумать, альтернатива сортировке части массива - просто перевернуть ее. Элементы всегда будут располагаться в порядке убывания, а затем должны располагаться в порядке возрастания. - person Guffa; 28.08.2009

arrow_upward
6
arrow_downward

Похоже, вы хотите сгенерировать перестановки своего списка в лексическом порядке. Эти условия поиска должны начать полезный путь.

Например, Python включает это в модуль itertools из версии 2.6 об. В этой документации показан код, реализующий такой алгоритм.

person Phil Miller    schedule 27.08.2009