Permutation of array

For example I have this array:

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

I need list of all permutations such that if one is like this, {3,2,1,4,6}, others must not be the same. I know that if the length of the array is n then there are n! possible combinations. How can this algorithm be written?

Update: thanks, but I need a pseudo code algorithm like:

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

Just algorithm. Yes, API functions are good, but it does not help me too much.

176368 次浏览
小开
最佳答案

如果使用 C + + ，可以使用 <algorithm>头文件中的 std::next_permutation:

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));
小开

Here is an implementation of the Permutation in Java:

排列-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() {
}


}
小开

下面是如何打印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-th 元素开始的所有排列。棘手的部分是，在递归调用之后，您必须将 i-th 元素与第一个元素交换回来，否则您可能会在第一个位置获得重复的值。通过将其交换回来，我们可以恢复元素的顺序(基本上可以进行回溯)。

重复值情况的迭代器和扩展

之前的算法的缺点是它是递归的，并且不能很好地使用迭代器。另一个问题是，如果在输入中允许重复元素，那么它就不能按原样工作。

例如，给定输入[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排列。

小开

3项递归解决方案的可视化表示形式: Http://www.docdroid.net/ea0s/generatepermutations.pdf.html

细目:

  1. 对于两项数组，有两种排列:
    • 原始数组，以及
    • 两个元素交换了
  2. 对于三项数组，有六种排列:
    • 那么底部两个元素的排列
    • 交换第一项和第二项，以及底部两个元素的排列
    • 交换第一项和第三项，以及底部两个元素的排列。
    • 从本质上说，每个项目都有机会在第一个插槽
小开

对于给定的数组大小 n有 n!总排列。

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

For input array [3,2,1,4,6], there are totally 5! = 120 possible permutations which are:

[[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]]

Hope this helps.

小开

一个简单的 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;
}
}
小开

基元数组示例:

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

像这样..。

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


}
小开

通过递归(动态编程)实现，在 爪哇咖啡,中使用测试用例(< em > TestNG )。

密码

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 (test case via 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

堆的算法生成 n 个对象的所有可能的排列。它最早是在1963年由 B.R.Heap 提出的。该算法使运动最小化: 它通过交换一对元素生成前一个元素的每个排列; 其他 n-2元素不受干扰。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.

因此，如果我们想要以递归的方式来做，Sudo 代码如下所示。

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 代码:

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, ',');
}
小开

这里是一个使用数组和 Java8 + 

import java.util.Arrays;
import java.util.stream.IntStream;


public class HelloWorld {


public static void main(String[] args) {
int[] arr = {1, 2, 3, 5};
permutation(arr, new int[]{});
}


static void permutation(int[] arr, int[] prefix) {
if (arr.length == 0) {
System.out.println(Arrays.toString(prefix));
}
for (int i = 0; i < arr.length; i++) {
int i2 = i;
int[] pre = IntStream.concat(Arrays.stream(prefix), IntStream.of(arr[i])).toArray();
int[] post = IntStream.range(0, arr.length).filter(i1 -> i1 != i2).map(v -> arr[v]).toArray();
permutation(post, pre);
}
}
}
小开

取代 排列，我们可以更好地称之为 组合 。

不管编码语言如何，我们可以使用一种简单的方法, 因此，使用 dynamic programming方法。

此代码也关注这些组合 没有邻居。

#include <iostream>
#include <vector>
using namespace std;


template <class myIterator, class T>
myIterator findDigit(myIterator first, myIterator last, T val)
{
while(first != last) {
if(*first == val) { break; }
first++;
}
return first;
}


void printCombinations(vector<vector<int>> combinations)
{
cout << "printing all " << combinations.size() << " combinations" << endl;
for(int i=0; i<combinations.size(); i++) {
cout << "[";
for(int j=0; j<combinations[i].size(); j++) {
cout << " " << combinations[i][j] << " ";
}
cout << "] , ";
}
return;
}


int main()
{
vector<int> a = {1,2,3,4,5};
vector<vector<int>> comb;
vector<int> t;
int len=a.size();


for(int i=0; i<len; i++) {
t.push_back(a.at(i));
comb.push_back(t);
t.clear();
}


for(int l=1; l<len; l++) {
for(int j=0; j<comb.size(); j++) {
if(comb[j].size()==l) {
int t = comb[j].back();
if(t != a.back()) {
vector<int>::iterator it = findDigit(a.begin(), a.end(), t);
for(std::vector<int>::iterator k=it+1; k!=a.end();k++) {
vector<int> t (comb[j].begin(), comb[j].end());
t.push_back(*k);
comb.push_back(t);
t.clear();
}
}
}
}
}


printCombinations(comb);
return 0;
}

Although the complexity is a bit high, it's definitely lower than the recursion approach, especially when the array size is very large.

上述数组(或向量，如果你愿意)的输出是:

printing all 31 combinations
[ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ], [ 1  2 ], [ 1  3 ], [ 1  4 ], [ 1  5 ], [ 2  3 ], [ 2  4 ], [ 2  5 ], [ 3  4 ], [ 3  5 ], [ 4  5 ], [ 1
2  3 ], [ 1  2  4 ], [ 1  2  5 ], [ 1  3  4 ], [ 1  3  5 ], [ 1  4  5 ], [ 2  3  4 ], [ 2  3  5 ], [ 2  4  5 ], [ 3  4  5 ], [ 1  2  3  4
], [ 1  2  3  5 ], [ 1  2  4  5 ], [ 1  3  4  5 ], [ 2  3  4  5 ], [ 1  2  3  4  5 ],

该代码也可以用于字符和字符串，只要在需要的地方替换数据类型即可。

例如。

vector<char> a = {'d','g','y','u','t'};

给予

printing all 31 combinations
[ d ] , [ g ] , [ y ] , [ u ] , [ t ] , [ d  g ] , [ d  y ] , [ d  u ] , [ d  t ] , [ g  y ] , [ g  u ] , [ g  t ] , [ y  u ] , [ y  t ] ,
[ u  t ] , [ d  g  y ] , [ d  g  u ] , [ d  g  t ] , [ d  y  u ] , [ d  y  t ] , [ d  u  t ] , [ g  y  u ] , [ g  y  t ] , [ g  u  t ] , [
y  u  t ] , [ d  g  y  u ] , [ d  g  y  t ] , [ d  g  u  t ] , [ d  y  u  t ] , [ g  y  u  t ] , [ d  g  y  u  t ] ,

还有

vector<string> a = {"asdf","myfl", "itshot", "holy"};

给予

printing all 15 combinations
[ asdf ] , [ myfl ] , [ itshot ] , [ holy ] , [ asdf  myfl ] , [ asdf  itshot ] , [ asdf  holy ] , [ myfl  itshot ] , [ myfl  holy ] , [ itshot  holy ] , [ asdf  myfl  itshot ] , [ asdf  myfl  holy ] , [ asdf  itshot  holy ] , [ myfl  itshot  holy ] , [ asdf  myfl  itshot  holy ] ,

提交答案