Алгоритм для перемещения элементов в массиве
-
20-09-2019 - |
Вопрос
Рассмотрим следующий сценарий.
У меня есть множество чисел:
[ 1,2,3,4 ]
Если бы этот массив был присоединен, у меня будет номер 1234.
Я хочу поменять цифры, чтобы достичь Scoss Mest Lighter.
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
Решение
Это дает вам следующую перестановку:
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. Предметы всегда находятся в порядке убывания и должны быть в порядке возрастания, поэтому они дают тот же результат.
Другие советы
Похоже, вы хотите генерировать перестановки вашего списка в лексический порядок. Анкет Эти поисковые термины должны начать вас по полезному пути.
Например, Python включает в себя это в итул Модуль из версии 2.6 на. Эта документация показывает код, который реализует такой алгоритм.