배열의 순열

배열의 순열

---

예를 들어 다음 배열이 있습니다.

int a[] = new int[]{3,4,6,2,1};

하나가 이와 같으면 다른 순열이 {3,2,1,4,6}동일하지 않아야하는 모든 순열 목록이 필요합니다 . 배열의 길이가 n 이면 n 이 있다는 것을 압니다 ! 가능한 조합. 이 알고리즘을 어떻게 작성할 수 있습니까?

업데이트 : 감사합니다.하지만 다음과 같은 의사 코드 알고리즘이 필요합니다.

for(int i=0;i<a.length;i++){
    // code here
}

그냥 알고리즘. 예, API 기능은 좋지만 그다지 도움이되지는 않습니다.

---

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 번 나오며,이 경우에는 당연히보고 싶은 것이 아닙니다. 그러한 순열의 수는 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의 순열 구현입니다.

순열-자바

당신은 그것에 대해 확인해야합니다!

편집 : 링크 죽음으로부터 보호하기 위해 아래에 붙여 넣은 코드 :

// 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. 다음은 DFS를 사용하여 Java로 작성된 코드입니다.

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. 3 개 항목 배열의 경우 6 개의 순열이 있습니다.
   • 하단 두 요소의 순열
   • 첫 번째와 두 번째 항목과 하위 두 요소의 순열을 바꿉니다.
   • 첫 번째와 세 번째 항목과 하위 두 요소의 순열을 바꿉니다.
   • 기본적으로 각 항목은 첫 번째 슬롯에서 기회를 얻습니다.

---

간단한 자바 구현, 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);
            }
        }
    }

}

---

테스트 케이스 ( TestNG )를 사용 하여 Java 에서 재귀 (동적 프로그래밍)를 통한 구현 .

---

암호

PrintPermutation.java

import java.util.Arrays;

/**
 * Print permutation of n elements.
 * 
 * @author eric
 * @date Oct 13, 2018 12:28:10 PM
 */
public class PrintPermutation {
    /**
     * Print permutation of array elements.
     * 
     * @param arr
     * @return count of permutation,
     */
    public static int permutation(int arr[]) {
        return permutation(arr, 0);
    }

    /**
     * Print permutation of part of array elements.
     * 
     * @param arr
     * @param n
     *            start index in array,
     * @return count of permutation,
     */
    private static int permutation(int arr[], int n) {
        int counter = 0;
        for (int i = n; i < arr.length; i++) {
            swapArrEle(arr, i, n);
            counter += permutation(arr, n + 1);
            swapArrEle(arr, n, i);
        }
        if (n == arr.length - 1) {
            counter++;
            System.out.println(Arrays.toString(arr));
        }

        return counter;
    }

    /**
     * swap 2 elements in array,
     * 
     * @param arr
     * @param i
     * @param k
     */
    private static void swapArrEle(int arr[], int i, int k) {
        int tmp = arr[i];
        arr[i] = arr[k];
        arr[k] = tmp;
    }
}

PrintPermutationTest.java (테스트 케이스를 통해TestNG)

import org.testng.Assert;
import org.testng.annotations.Test;

/**
 * PrintPermutation test.
 * 
 * @author eric
 * @date Oct 14, 2018 3:02:23 AM
 */
public class PrintPermutationTest {
    @Test
    public void test() {
        int arr[] = new int[] { 0, 1, 2, 3 };
        Assert.assertEquals(PrintPermutation.permutation(arr), 24);

        int arrSingle[] = new int[] { 0 };
        Assert.assertEquals(PrintPermutation.permutation(arrSingle), 1);

        int arrEmpty[] = new int[] {};
        Assert.assertEquals(PrintPermutation.permutation(arrEmpty), 0);
    }
}

---

위키 https://en.wikipedia.org/wiki/Heap%27s_algorithm 에 따르면

Heap's algorithm generates all possible permutations of n objects. It was first proposed by B. R. Heap in 1963. The algorithm minimizes movement: it generates each permutation from the previous one by interchanging a single pair of elements; the other n−2 elements are not disturbed. In a 1977 review of permutation-generating algorithms, Robert Sedgewick concluded that it was at that time the most effective algorithm for generating permutations by computer.

So if we want to do it in recursive manner, Sudo code is bellow.

procedure generate(n : integer, A : array of any):
    if n = 1 then
          output(A)
    else
        for i := 0; i < n - 1; i += 1 do
            generate(n - 1, A)
            if n is even then
                swap(A[i], A[n-1])
            else
                swap(A[0], A[n-1])
            end if
        end for
        generate(n - 1, A)
    end if

java code:

public static void printAllPermutations(
        int n, int[] elements, char delimiter) {
    if (n == 1) {
        printArray(elements, delimiter);
    } else {
        for (int i = 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);
    }
}

private static void printArray(int[] input, char delimiter) {
    int i = 0;
    for (; i < input.length; i++) {
        System.out.print(input[i]);
    }
    System.out.print(delimiter);
}

private static void swap(int[] input, int a, int b) {
    int tmp = input[a];
    input[a] = input[b];
    input[b] = tmp;
}

public static void main(String[] args) {
    int[] input = new int[]{0,1,2,3};
    printAllPermutations(input.length, input, ',');
}

참고URL : https://stackoverflow.com/questions/2920315/permutation-of-array