1. Въведение
В тази статия ще разгледаме как да създадем пермутации на масив.
Първо ще определим какво е пермутация. Второ, ще разгледаме някои ограничения. И трето, ще разгледаме три начина за изчисляването им: рекурсивно, итеративно и произволно.
Ще се съсредоточим върху внедряването в Java и следователно няма да навлизаме в много математически подробности.
2. Какво е пермутация?
Пермутацията на набор е пренареждане на неговите елементи. Набор, който се състои от n елемента, има n! пермутации. Тук n! е факториалът, който е произведение на всички положителни числа, по-малки или равни на n .
2.1. Пример
Масивът от цели числа [3,4,7] има три елемента и шест пермутации:
н! = 3! = 1 х 2 х 3 = 6
Пермутации: [3,4,7]; [3,7,4]; [4,7,3]; [4,3,7]; [7,3,4]; [7,4,3]
2.2. Ограничения
Броят на пермутациите се увеличава бързо с n . Докато генерирането на всички пермутации от десет елемента отнема само няколко секунди, генерирането на всички пермутации от 15 елемента ще отнеме две седмици:
3. Алгоритми
3.1. Рекурсивен алгоритъм
Първият алгоритъм, който разглеждаме, е алгоритъмът на Heap. Това е рекурсивен алгоритъм, който произвежда всички пермутации чрез размяна на един елемент на итерация.
Входният масив ще бъде модифициран. Ако не искаме това, трябва да създадем копие на масива, преди да извикаме метода:
public static void printAllRecursive( int n, T[] elements, char delimiter) { if(n == 1) { printArray(elements, delimiter); } else { for(int i = 0; i < n-1; i++) { printAllRecursive(n - 1, elements, delimiter); if(n % 2 == 0) { swap(elements, i, n-1); } else { swap(elements, 0, n-1); } } printAllRecursive(n - 1, elements, delimiter); } } Методът използва два помощни метода:
private void swap(T[] input, int a, int b) { T tmp = input[a]; input[a] = input[b]; input[b] = tmp; }private void printArray(T[] input) { System.out.print('\n'); for(int i = 0; i < input.length; i++) { System.out.print(input[i]); } } Тук записваме резултата в System.out , но вместо това можем лесно да съхраним резултата в масив или в списък.
3.2. Итеративен алгоритъм
Алгоритъмът на Heap може също да бъде реализиран с помощта на итерации:
int[] indexes = new int[n]; int[] indexes = new int[n]; for (int i = 0; i < n; i++) { indexes[i] = 0; } printArray(elements, delimiter); int i = 0; while (i < n) { if (indexes[i] < i) { swap(elements, i % 2 == 0 ? 0: indexes[i], i); printArray(elements, delimiter); indexes[i]++; i = 0; } else { indexes[i] = 0; i++; } } 3.3. Пермутации в лексикографски ред
Ако елементите са сравними, можем да генерираме пермутации, сортирани по естествения ред на елементите:
public static
void printAllOrdered( T[] elements, char delimiter) { Arrays.sort(elements); boolean hasNext = true; while(hasNext) { printArray(elements, delimiter); int k = 0, l = 0; hasNext = false; for (int i = elements.length - 1; i > 0; i--) { if (elements[i].compareTo(elements[i - 1]) > 0) { k = i - 1; hasNext = true; break; } } for (int i = elements.length - 1; i > k; i--) { if (elements[i].compareTo(elements[k]) > 0) { l = i; break; } } swap(elements, k, l); Collections.reverse(Arrays.asList(elements).subList(k + 1, elements.length)); } }
Този алгоритъм има обратна операция във всяка итерация и следователно е по-малко ефективен за масиви от алгоритъма на Heap.
3.4. Рандомизиран алгоритъм
Ако n е голямо, можем да генерираме произволна пермутация чрез разбъркване на масива:
Collections.shuffle(Arrays.asList(elements));Можем да направим това няколко пъти, за да генерираме извадка от пермутации.
Може да създадем едни и същи пермутации повече от веднъж, но за големи стойности на n шансовете да генерираме една и съща пермутация два пъти са ниски.
4. Заключение
Има много начини за генериране на всички пермутации на масив. В тази статия видяхме рекурсивния и итеративен алгоритъм на Heap и как да генерираме сортиран списък с пермутации.
Не е възможно да се генерират всички пермутации за големи масиви, следователно вместо това можем да генерираме случайни пермутации.
Внедряването на всички кодови фрагменти в тази статия може да бъде намерено в нашето хранилище на Github.