Перестановка блока
у меня есть этот массив:
int a[] = new int[]{3,4,6,2,1};
мне нужен список всех перестановок таких, что если один такой, {3,2,1,4,6}, другие люди не должны быть одинаковыми. Я знаю, что если длина массива n здесь n! возможных комбинаций. Как можно написать этот алгоритм?
Update: спасибо, но мне нужен алгоритм псевдо-кода, например:
for(int i=0;i<a.length;i++){
// code here
}
просто алгоритм. Да, функции API хороши, но мне это тоже не помогает много.
9 ответов:
Если вы используете 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));
вот как вы можете напечатать все перестановки в 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] все возможные перестановки (без повторений) являются
[3, 3, 4, 4] [3, 4, 3, 4] [3, 4, 4, 3] [4, 3, 3, 4] [4, 3, 4, 3] [4, 4, 3, 3](если вы просто применить
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; } }вот полный код итератора. Конструктор принимает массив объектов и отображает их в массив целых чисел, используя
HashMap.import java.lang.reflect.Array; import java.util.*; class Permutations<E> implements Iterator<E[]>{ private E[] arr; private int[] ind; private boolean has_next; public E[] output;//next() returns this array, make it public Permutations(E[] arr){ this.arr = arr.clone(); ind = new int[arr.length]; //convert an array of any elements into array of integers - first occurrence is used to enumerate Map<E, Integer> hm = new HashMap<E, Integer>(); for(int i = 0; i < arr.length; i++){ Integer n = 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; } public boolean hasNext() { return has_next; } /** * Computes next permutations. Same array instance is returned every time! * @return */ public E[] next() { if (!has_next) throw new NoSuchElementException(); for(int i = 0; i < ind.length; i++){ output[i] = arr[ind[i]]; } //get next permutation has_next = false; 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); } has_next = true; break; } } return output; } private void swap(int[] arr, int i, int j){ int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } public void remove() { } }использование/тест:
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перестановок.
вот реализация перестановки в Java:
вы должны проверить это!
изменить: код вставлен ниже, чтобы защитить от link-death:
// Permute.java -- A class generating all permutations import java.util.Iterator; import java.util.NoSuchElementException; import java.lang.reflect.Array; public class Permute implements Iterator { private final int size; private final Object [] elements; // copy of original 0 .. size-1 private final Object ar; // array for output, 0 .. size-1 private final int [] permutation; // perm of nums 1..size, perm[0]=0 private boolean next = true; // int[], double[] array won't work :-( public Permute (Object [] e) { size = e.length; elements = new Object [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 = new int [size+1]; for (int i=0; i<size+1; i++) { permutation [i]=i; } } private void formNextPermutation () { 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]); } } public boolean hasNext() { return next; } public void remove() throws UnsupportedOperationException { throw new UnsupportedOperationException(); } private void swap (final int i, final int j) { final int x = permutation[i]; permutation[i] = permutation [j]; permutation[j] = x; } // does not throw NoSuchElement; it wraps around! public Object next() throws NoSuchElementException { formNextPermutation (); // copy original elements int i = size-1; while (permutation[i]>permutation[i+1]) i--; if (i==0) { next = false; for (int j=0; j<size+1; j++) { permutation [j]=j; } return ar; } int j = size; while (permutation[i]>permutation[j]) j--; swap (i,j); int r = size; int s = i+1; while (r>s) { swap(r,s); r--; s++; } return ar; } public String toString () { final int n = Array.getLength(ar); final StringBuffer sb = new StringBuffer ("["); for (int j=0; j<n; j++) { sb.append (Array.get(ar,j).toString()); if (j<n-1) sb.append (","); } sb.append("]"); return new String (sb); } public static void main (String [] args) { for (Iterator i = new Permute(args); i.hasNext(); ) { final String [] a = (String []) i.next(); System.out.println (i); } } }
Это 2-перестановка для списка, завернутого в итератор
import java.util.Iterator; import java.util.LinkedList; import java.util.List; /* all permutations of two objects * * for ABC: AB AC BA BC CA CB * * */ public class ListPermutation<T> implements Iterator { int index = 0; int current = 0; List<T> list; public ListPermutation(List<T> e) { list = e; } public boolean hasNext() { return !(index == list.size() - 1 && current == list.size() - 1); } public List<T> next() { if(current == index) { current++; } if (current == list.size()) { current = 0; index++; } List<T> output = new LinkedList<T>(); output.add(list.get(index)); output.add(list.get(current)); current++; return output; } public void remove() { } }
здесь
n!всего перестановок для данного размера массиваn. Вот код, написанный на Java с помощью DFS.public List<List<Integer>> permute(int[] nums) { List<List<Integer>> results = new ArrayList<List<Integer>>(); if (nums == null || nums.length == 0) { return results; } List<Integer> result = new ArrayList<>(); dfs(nums, results, result); return results; } public void dfs(int[] nums, List<List<Integer>> results, List<Integer> result) { if (nums.length == result.size()) { List<Integer> temp = new ArrayList<>(result); results.add(temp); } for (int i=0; i<nums.length; i++) { if (!result.contains(nums[i])) { result.add(nums[i]); dfs(nums, results, result); result.remove(result.size() - 1); } } }для входного массива [3,2,1,4,6], есть полностью 5! = 120 возможных перестановок, которые являются:
[[3,4,6,2,1],[3,4,6,1,2],[3,4,2,6,1],[3,4,2,1,6],[3,4,1,6,2],[3,4,1,2,6],[3,6,4,2,1],[3,6,4,1,2],[3,6,2,4,1],[3,6,2,1,4],[3,6,1,4,2],[3,6,1,2,4],[3,2,4,6,1],[3,2,4,1,6],[3,2,6,4,1],[3,2,6,1,4],[3,2,1,4,6],[3,2,1,6,4],[3,1,4,6,2],[3,1,4,2,6],[3,1,6,4,2],[3,1,6,2,4],[3,1,2,4,6],[3,1,2,6,4],[4,3,6,2,1],[4,3,6,1,2],[4,3,2,6,1],[4,3,2,1,6],[4,3,1,6,2],[4,3,1,2,6],[4,6,3,2,1],[4,6,3,1,2],[4,6,2,3,1],[4,6,2,1,3],[4,6,1,3,2],[4,6,1,2,3],[4,2,3,6,1],[4,2,3,1,6],[4,2,6,3,1],[4,2,6,1,3],[4,2,1,3,6],[4,2,1,6,3],[4,1,3,6,2],[4,1,3,2,6],[4,1,6,3,2],[4,1,6,2,3],[4,1,2,3,6],[4,1,2,6,3],[6,3,4,2,1],[6,3,4,1,2],[6,3,2,4,1],[6,3,2,1,4],[6,3,1,4,2],[6,3,1,2,4],[6,4,3,2,1],[6,4,3,1,2],[6,4,2,3,1],[6,4,2,1,3],[6,4,1,3,2],[6,4,1,2,3],[6,2,3,4,1],[6,2,3,1,4],[6,2,4,3,1],[6,2,4,1,3],[6,2,1,3,4],[6,2,1,4,3],[6,1,3,4,2],[6,1,3,2,4],[6,1,4,3,2],[6,1,4,2,3],[6,1,2,3,4],[6,1,2,4,3],[2,3,4,6,1],[2,3,4,1,6],[2,3,6,4,1],[2,3,6,1,4],[2,3,1,4,6],[2,3,1,6,4],[2,4,3,6,1],[2,4,3,1,6],[2,4,6,3,1],[2,4,6,1,3],[2,4,1,3,6],[2,4,1,6,3],[2,6,3,4,1],[2,6,3,1,4],[2,6,4,3,1],[2,6,4,1,3],[2,6,1,3,4],[2,6,1,4,3],[2,1,3,4,6],[2,1,3,6,4],[2,1,4,3,6],[2,1,4,6,3],[2,1,6,3,4],[2,1,6,4,3],[1,3,4,6,2],[1,3,4,2,6],[1,3,6,4,2],[1,3,6,2,4],[1,3,2,4,6],[1,3,2,6,4],[1,4,3,6,2],[1,4,3,2,6],[1,4,6,3,2],[1,4,6,2,3],[1,4,2,3,6],[1,4,2,6,3],[1,6,3,4,2],[1,6,3,2,4],[1,6,4,3,2],[1,6,4,2,3],[1,6,2,3,4],[1,6,2,4,3],[1,2,3,4,6],[1,2,3,6,4],[1,2,4,3,6],[1,2,4,6,3],[1,2,6,3,4],[1,2,6,4,3]]надеюсь, что это помогает.
пример с примитивным массивом:
public static void permute(int[] intArray, int start) { for(int i = start; i < intArray.length; i++){ int temp = intArray[start]; intArray[start] = intArray[i]; intArray[i] = temp; permute(intArray, start + 1); intArray[i] = intArray[start]; intArray[start] = temp; } if (start == intArray.length - 1) { System.out.println(java.util.Arrays.toString(intArray)); } } public static void main(String[] args){ int intArr[] = {1, 2, 3}; permute(intArr, 0); }
визуальное представление рекурсивного решения из 3 элементов: http://www.docdroid.net/ea0s/generatepermutations.pdf.html
поломки:
- для массива из двух элементов существует две перестановки:
- исходный массив, и
- два элемента меняются местами
- для массива из трех элементов существует шесть перестановок:
- перестановки нижних двух элементов, тогда
- поменять местами 1-й и 2-й элементы, а также перестановки двух нижних элементов
- поменять местами 1-й и 3-й элементы, а также перестановки нижних двух элементов.
- по сути, каждый из элементов получает свой шанс в первом слоте
простая реализация java, см. c++
std::next_permutation:public static void main(String[] args){ int[] list = {1,2,3,4,5}; List<List<Integer>> output = new Main().permute(list); for(List result: output){ System.out.println(result); } } public List<List<Integer>> permute(int[] nums) { List<List<Integer>> list = new ArrayList<List<Integer>>(); int size = factorial(nums.length); // add the original one to the list List<Integer> seq = new ArrayList<Integer>(); for(int a:nums){ seq.add(a); } list.add(seq); // generate the next and next permutation and add them to list for(int i = 0;i < size - 1;i++){ seq = new ArrayList<Integer>(); nextPermutation(nums); for(int a:nums){ seq.add(a); } list.add(seq); } return list; } int factorial(int n){ return (n==1)?1:n*factorial(n-1); } void nextPermutation(int[] nums){ int i = nums.length -1; // start from the end while(i > 0 && nums[i-1] >= nums[i]){ i--; } if(i==0){ reverse(nums,0,nums.length -1 ); }else{ // found the first one not in order int j = i; // found just bigger one while(j < nums.length && nums[j] > nums[i-1]){ j++; } //swap(nums[i-1],nums[j-1]); int tmp = nums[i-1]; nums[i-1] = nums[j-1]; nums[j-1] = tmp; reverse(nums,i,nums.length-1); } } // reverse the sequence void reverse(int[] arr,int start, int end){ int tmp; for(int i = 0; i <= (end - start)/2; i++ ){ tmp = arr[start + i]; arr[start + i] = arr[end - i]; arr[end - i ] = tmp; } }
сделайте так...
import java.util.ArrayList; import java.util.Arrays; public class rohit { public static void main(String[] args) { ArrayList<Integer> a=new ArrayList<Integer>(); ArrayList<Integer> b=new ArrayList<Integer>(); b.add(1); b.add(2); b.add(3); permu(a,b); } public static void permu(ArrayList<Integer> prefix,ArrayList<Integer> value) { if(value.size()==0) { System.out.println(prefix); } else { for(int i=0;i<value.size();i++) { ArrayList<Integer> a=new ArrayList<Integer>(); a.addAll(prefix); a.add(value.get(i)); ArrayList<Integer> b=new ArrayList<Integer>(); b.addAll(value.subList(0, i)); b.addAll(value.subList(i+1, value.size())); permu(a,b); } } } }