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

Question

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

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

 [ 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

Answer 1

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

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;
}

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

Answer 2

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

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