CareerCup

similar : stackoverflow_com/questions/20906214/permutation-algorithm-for-array-of-integers-in-java

Recursive solution using python.

def generate(remaining):
  # Base cases
  if not remaining:
    return None
  
  if len(remaining) == 1:
    return [remaining]
  
  last_e = remaining[-1]
  subarray = remaining[0:-1]
  subsolutions = generate(subarray)  # Recursive call to solve a sub problem
  
  # Insert the last element in every single index
  new_solutions = []
  if subsolutions:
    for subsol in subsolutions:
      for i in range(len(subarray) + 1):  # Include the end of the list
        new_array = list(subsol)          # Have to copy the list in order to modify it
        new_array.insert(i, last_e)
        new_solutions.append(new_array)
  return new_solutions

x = generate([1, 2, 3])

You need to consider whether there are duplicates

"""
Generate all permutations of given sequence
of elements.
Return a list of all distinct permutations.

E.g.
generate([1, 2, 3]) ->
[1, 2, 3], [1, 3, 2], [2, 3, 1],
[2, 1, 3], [3, 1, 2], [3, 2, 1]
"""


_results = []


def perm(A):
    global _results
    A = sorted(A)
    _results = []
    _aux([], A)
    return _results


def _aux(one_result, remain):
    global _results
    if not remain:
        _results.append(one_result)
    else:
        num = len(remain)
        for i in range(num):
            if i > 0 and remain[i - 1] == remain[i]:
                continue
            else:
                _aux(one_result + [remain[i]],
                     remain[:i] + remain[i + 1:])

package linkedin;

import org.junit.Test;

import java.util.*;

import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertEquals;

public class Permutations {
List<int[]> expected = Arrays.asList(
new int[]{1, 2, 3},
new int[]{2, 1, 3},
new int[]{2, 3, 1},
new int[]{1, 3, 2},
new int[]{3, 1, 2},
new int[]{3, 2, 1}
);

@Test
public void test() {
List<int[]> actual = permutations(new int[]{1, 2, 3}, 0);
assertEquals(expected.size(), actual.size());

Iterator<int[]> actualIt = actual.iterator();
Iterator<int[]> expectedIt = expected.iterator();
while (actualIt.hasNext()) {
assertArrayEquals(expectedIt.next(), actualIt.next());
}
}

private List<int[]> permutations(int[] a, int s) {
if (a.length == 0 || s == a.length) return Collections.emptyList();
if (s == a.length - 1) return Collections.singletonList(new int[]{a[s]});
List<int[]> permsAfter = permutations(a, s + 1);
List<int[]> res = new ArrayList<>(permsAfter.size() * (permsAfter.get(0).length + 1));
for (int[] permAfter : permsAfter) {
for (int i = 0; i < permAfter.length + 1; i++) {
int[] perm = new int[permAfter.length + 1];
for (int j = 0; j < perm.length; j++) {
perm[j] = (i == j ? a[s] : (i < j ? permAfter[j - 1] : permAfter[j]));
}
res.add(perm);
}
}
return res;
}
}

With formatting.

package linkedin;

import org.junit.Test;

import java.util.*;

import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertEquals;

public class Permutations {
    List<int[]> expected = Arrays.asList(
            new int[]{1, 2, 3},
            new int[]{2, 1, 3},
            new int[]{2, 3, 1},
            new int[]{1, 3, 2},
            new int[]{3, 1, 2},
            new int[]{3, 2, 1}
    );

    @Test
    public void test() {
        List<int[]> actual = permutations(new int[]{1, 2, 3}, 0);
        assertEquals(expected.size(), actual.size());

        Iterator<int[]> actualIt = actual.iterator();
        Iterator<int[]> expectedIt = expected.iterator();
        while (actualIt.hasNext()) {
            assertArrayEquals(expectedIt.next(), actualIt.next());
        }
    }

    private List<int[]> permutations(int[] a, int s) {
        if (a.length == 0 || s == a.length) return Collections.emptyList();
        if (s == a.length - 1) return Collections.singletonList(new int[]{a[s]});
        List<int[]> permsAfter = permutations(a, s + 1);
        List<int[]> res = new ArrayList<>(permsAfter.size() * (permsAfter.get(0).length + 1));
        for (int[] permAfter : permsAfter) {
            for (int i = 0; i < permAfter.length + 1; i++) {
                int[] perm = new int[permAfter.length + 1];
                for (int j = 0; j < perm.length; j++) {
                    perm[j] = (i == j ? a[s] : (i < j ? permAfter[j - 1] : permAfter[j]));
                }
                res.add(perm);
            }
        }
        return res;
    }
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Permutation {

	private List<List<Integer>> results = new ArrayList<List<Integer>>();
	
	
	public void perm(List<Integer> result, List<Integer> remaining) {
		
		if(remaining.size() == 0) {
			results.add(result);
		}
		
		for (int i=0; i<remaining.size(); i++) {
			if(i>0 && remaining.get(i-1) == remaining.get(i)) {
				continue;
			}
			
			List<Integer> copy1 = new ArrayList<Integer>(result);
			copy1.add(remaining.get(i));
			List<Integer> copy2 = new ArrayList<Integer>(remaining);
			copy2.remove(i);
			perm(copy1, copy2);
		}
	}
	
	public void print() {
		for(List<Integer> result : results) {
			for(Integer i : result) {
				System.out.print(i + " ");
			}
			System.out.println();
		}
	}
	
	public static void main(String[] args) {
		Permutation p = new Permutation();
		List<Integer> input = Arrays.asList(1,1,2,3);
		p.perm(new ArrayList<Integer>(), input);
		p.print();
	}

}

bool perm_next (int *a, int n)
{   
    int k = n - 2;

    if (k < 0) return false;

    // Find the largest index k such that a[k] < a[k + 1]. If no such index
    // exists, the permutation is the last permutation.
    //
    while (a[k] >= a[k+1]) {
        k--; 
        if (k < 0)
            return false;
    }

    // Find the largest index l such that a[k] < a[l]. Since k + 1 is such an
    // index, l is well defined and satisfies k < l.
    int l = n - 1;
    while (a[k] >= a[l])
        l--;

    // Swap a[k] with a[l]
    std::swap(a[k], a[l]);

    // Reverse the sequence from a[k + 1] up to and including the final
    // element a[n]
    std::reverse(&a[k+1], &a[n]);

    return true;
}

int main()
{
    int a[N];

    for (int i = 0; i < N; i++)
        a[i] = i + 1;

    do {
        print(a, N);
    } while (perm_next(a, N));

    return 0;
}