Перестановка массива

Question

Например у меня есть этот массив:

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 
} 

алгоритма Just. Да, функции API хороши, но это не очень помогает мне.

Answer 1

Если вы используете 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)); 

Answer 2

Вот реализация перестановки в Java:

Permutation - Java

Вы должны иметь проверить его!

Edit: код вставил ниже для защиты от установления связи смерти:

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

Answer 3

Это 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() { 
    } 

} 

Answer 4

Вот как вы можете напечатать все перестановки в 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)

Можно изменить вышеупомянутый алгоритм для обработки этого случая, но он не будет выглядеть красиво. К счастью, есть лучший алгоритм (я нашел его here), который обрабатывает повторяющиеся значения и не является рекурсивным.

Прежде всего обратите внимание, что перестановка массива любых объектов может быть сведена к перестановкам целых чисел, перечислив их в любом порядке.

Чтобы получить перестановки целочисленного массива, вы начинаете с массива, отсортированного по возрастанию. Вы «цель» - сделать его нисходящим. Чтобы сгенерировать следующую перестановку, вы пытаетесь найти первый индекс снизу, где последовательность не спускается, и улучшает значение в этом индексе, в то время как порядок переключения остальной части хвоста от нисходящего к восходящему в этом случае.

Вот ядро ​​алгоритма:

//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 перестановки.

Answer 5

Визуальное представление 3-позиционным рекурсивного решения: http://www.docdroid.net/ea0s/generatepermutations.pdf.html

Разбивка:

1. Для массива два элемента, есть две перестановки:
   • Исходный массив и
   • Эти два элемента заменены
2. Для массива три элемента, есть шесть перестановок:
   • Перестановки нижних двух элементов, то
   • Замена 1-й и 2-й пункты и перестановки двух нижних элементов
   • Замена 1-й и 3-й элементы и перестановки нижних двух элементов.
   • По существу, каждый из элементов получает свой шанс в первом слоте

Answer 6

Есть 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]] 

Надеюсь, что это поможет.

Answer 7

Простая реализация 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; 
    } 
} 

Answer 8

Пример с примитивным массива:

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

Answer 9

ли, как это ...

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

}