Мне нужен список всех перестановок таким образом, чтобы, если одна из них была такой, {3,2,1,4,6} другие не должны совпадать. Я знаю, что если длина массива равна n, то существует n! возможных комбинаций. Как можно написать этот алгоритм?
Обновление: спасибо, но мне нужен алгоритм псевдокода типа:
for(int i=0;i<a.length;i++){ // code here }
Просто алгоритм. Да, функции API хороши, но мне это не слишком помогает.
Переведено автоматически
Ответ 1
Вот как вы можете напечатать все перестановки в 10 строках кода:
public class Permute{ static void permute(java.util.List<Integer> arr, int k){ for(int i = k; i < arr.size(); i++){ java.util.Collections.swap(arr, i, k); permute(arr, k+1); java.util.Collections.swap(arr, k, i); } if (k == arr.size() -1){ System.out.println(java.util.Arrays.toString(arr.toArray())); } } public static void main(String[] args){ Permute.permute(java.util.Arrays.asList(3,4,6,2,1), 0); } }
Вы берете первый элемент массива (k = 0) и заменяете его любым элементом (i) массива. Затем вы рекурсивно применяете перестановку к массиву, начиная со второго элемента. Таким образом, вы получите все перестановки, начинающиеся с i-го элемента. Сложность заключается в том, что после рекурсивного вызова вы должны поменять местами i-й элемент с первым элементом обратно, иначе вы могли бы получить повторяющиеся значения в первом месте. Меняя его местами, мы восстанавливаем порядок элементов (в основном вы выполняете обратный поиск).
Итераторы и расширение на случай повторяющихся значений
Недостатком предыдущего алгоритма является то, что он рекурсивен и плохо работает с итераторами. Другая проблема заключается в том, что если вы разрешаете повторяющиеся элементы во входных данных, то он не будет работать как есть.
Например, при заданных входных данных [3,3,4,4] все возможные перестановки (без повторений) являются
(если вы просто примените permute функцию сверху, вы получите [3,3,4,4] четыре раза, и это не то, что вы, естественно, хотите видеть в данном случае; и количество таких перестановок равно 4!/(2!*2!)=6)
Можно модифицировать приведенный выше алгоритм для обработки этого случая, но это будет выглядеть некрасиво. К счастью, есть алгоритм получше (я нашел его здесь), который обрабатывает повторяющиеся значения и не является рекурсивным.
Во-первых, обратите внимание, что перестановка массива любых объектов может быть сведена к перестановкам целых чисел путем перечисления их в любом порядке.
Чтобы получить перестановки массива целых чисел, вы начинаете с массива, отсортированного в порядке возрастания. Ваша "цель" - сделать его убывающим. Чтобы сгенерировать следующую перестановку, вы пытаетесь найти первый индекс снизу, где последовательность не является убывающей, и улучшаете значение в этом индексе, переключая порядок остальной части хвоста с убывающего на возрастающий в этом случае.
Вот суть алгоритма:
//ind is an array of integers for(int tail = ind.length - 1;tail > 0;tail--){ if (ind[tail - 1] < ind[tail]){//still increasing
//find last element which does not exceed ind[tail-1] int s = ind.length - 1; while(ind[tail-1] >= ind[s]) s--;
swap(ind, tail-1, s);
//reverse order of elements in the tail for(int i = tail, j = ind.length - 1; i < j; i++, j--){ swap(ind, i, j); } break; } }
Вот полный код iterator . Конструктор принимает массив объектов и преобразует их в массив целых чисел с помощью HashMap.
public E[] output;//next() returns this array, make it public
Permutations(E[] arr){ this.arr = arr.clone(); ind = newint[arr.length]; //convert an array of any elements into array of integers - first occurrence is used to enumerate Map<E, Integer> hm = newHashMap<E, Integer>(); for(inti=0; i < arr.length; i++){ Integern= hm.get(arr[i]); if (n == null){ hm.put(arr[i], i); n = i; } ind[i] = n.intValue(); } Arrays.sort(ind);//start with ascending sequence of integers
//output = new E[arr.length]; <-- cannot do in Java with generics, so use reflection output = (E[]) Array.newInstance(arr.getClass().getComponentType(), arr.length); has_next = true; }
publicbooleanhasNext() { return has_next; }
/** * Computes next permutations. Same array instance is returned every time! * @return */ public E[] next() { if (!has_next) thrownewNoSuchElementException();
for(inti=0; i < ind.length; i++){ output[i] = arr[ind[i]]; }
//get next permutation has_next = false; for(inttail= ind.length - 1;tail > 0;tail--){ if (ind[tail - 1] < ind[tail]){//still increasing
//find last element which does not exceed ind[tail-1] ints= ind.length - 1; while(ind[tail-1] >= ind[s]) s--;
swap(ind, tail-1, s);
//reverse order of elements in the tail for(inti= tail, j = ind.length - 1; i < j; i++, j--){ swap(ind, i, j); } has_next = true; break; }
} return output; }
privatevoidswap(int[] arr, int i, int j){ intt= arr[i]; arr[i] = arr[j]; arr[j] = t; }
publicvoidremove() {
} }
Использование / тест:
TCMath.Permutations<Integer> perm = new TCMath.Permutations<Integer>(new Integer[]{3,3,4,4,4,5,5}); int count = 0; while(perm.hasNext()){ System.out.println(Arrays.toString(perm.next())); count++; } System.out.println("total: " + count);
Выводит все 7!/(2!*3!*2!)=210 перестановки.
Ответ 2
Если вы используете C ++, вы можете использовать std::next_permutation из <algorithm> заголовочного файла:
int a[] = {3,4,6,2,1}; int size = sizeof(a)/sizeof(a[0]); std::sort(a, a+size); do { // print a's elements } while(std::next_permutation(a, a+size));
privatefinalint size; privatefinal Object [] elements; // copy of original 0 .. size-1 privatefinal Object ar; // array for output, 0 .. size-1 privatefinalint [] permutation; // perm of nums 1..size, perm[0]=0
privatebooleannext=true;
// int[], double[] array won't work :-( publicPermute(Object [] e) { size = e.length; elements = newObject [size]; // not suitable for primitives System.arraycopy (e, 0, elements, 0, size); ar = Array.newInstance (e.getClass().getComponentType(), size); System.arraycopy (e, 0, ar, 0, size); permutation = newint [size+1]; for (int i=0; i<size+1; i++) { permutation [i]=i; } }
privatevoidformNextPermutation() { for (int i=0; i<size; i++) { // i+1 because perm[0] always = 0 // perm[]-1 because the numbers 1..size are being permuted Array.set (ar, i, elements[permutation[i+1]-1]); } }
Алгоритм Heap генерирует все возможные перестановки n объектов. Впервые он был предложен Б. Р. Хипом в 1963 году. Алгоритм минимизирует перемещение: он генерирует каждую перестановку из предыдущей путем замены одной пары элементов; остальные n−2 элемента не нарушаются. В обзоре алгоритмов генерации перестановок 1977 года Роберт Седжвик пришел к выводу, что на тот момент это был наиболее эффективный алгоритм для генерации перестановок компьютером.
Итак, если мы хотим сделать это рекурсивным способом, ниже приведен код Sudo.
proceduregenerate(n : integer, A : arrayof any): if n = 1then output(A) else for i := 0; i < n - 1; i += 1do generate(n - 1, A) if n is even then swap(A[i], A[n-1]) else swap(A[0], A[n-1]) endif endfor generate(n - 1, A) endif
java-код:
publicstaticvoidprintAllPermutations( int n, int[] elements, char delimiter) { if (n == 1) { printArray(elements, delimiter); } else { for (inti=0; i < n - 1; i++) { printAllPermutations(n - 1, elements, delimiter); if (n % 2 == 0) { swap(elements, i, n - 1); } else { swap(elements, 0, n - 1); } } printAllPermutations(n - 1, elements, delimiter); } }
privatestaticvoidprintArray(int[] input, char delimiter) { inti=0; for (; i < input.length; i++) { System.out.print(input[i]); } System.out.print(delimiter); }
privatestaticvoidswap(int[] input, int a, int b) { inttmp= input[a]; input[a] = input[b]; input[b] = tmp; }