Getting ALL permutations of ALL sublists of a list of integers

Question

I've been having trouble with this problem. Basically, I have a list of integers, such as

list = [1, 2, 3]

I want to get all possible permutations of every subset. I know similar questions exist online, but I couldn't find one that does every permutation as well as every subset. In other words, I want:

function(list) = 
[], [1], [2], [3],
[1, 2], [2, 1], [1, 3], [3,1], [2, 3], [3,2],
[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]

I understand the output will get extremely large even for a small input list size. Unfortunately, I just cannot figure out how to do such a problem.

Thank you!

You seem to have figured out the answer to your own question in the example you've posted. Why can't you just write down a list of the steps you took and call that an algorithm ? — High Performance Mark, Jun 29 '15 at 20:29
More specifically, I'm having trouble turning it into java code, since I'm not really sure exactly what I'm doing... — jj172, Jun 29 '15 at 20:30

score 2 · Answer 1 · 2015-06-30T04:55:16.680

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;

public class Test {

private static boolean[] used;
private static int[] a;

private static void f(int curCount,int subsetSize,ArrayDeque<Integer> perm){
   // System.out.println("in rec "+curCount+" "+subsetSize);
    if(curCount < subsetSize){
        for(int i=0;i<a.length;i++) {
            if (!used[i]) { // try to add i-th elem of array  as a next element of  permutation if it's not busy
                perm.add(a[i]);
                used[i] = true; //mark i-th element as used for  future recursion calls
                f(curCount + 1, subsetSize,perm); // curCount+1 because we added elem to perm. subsetSize is const and it's needed just for recursion exit condition
                used[i] = false; // "free" i-th element
                perm.removeLast();
            }
        }
    }
    else{ //some permutation of array subset with size=subsetSize generated
        for(Integer xx:perm) System.out.print(xx+" ");
        System.out.println();

    }
}

public static void main(String[] args){

  a = new int[]{1,2,3};
  used = new boolean[a.length];
  Arrays.fill(used, false);

  // second param is a subset size (all sizes from 1 to n)
  // first param is number of "collected" numbers, when collected numbers==required subset size (firstparam==second param) exit from recursion (from some particular call-chain)
  // third param is data structure for constructing permutation
  for(int i=1;i<=a.length;i++)f(0,i,new ArrayDeque<Integer>());

} //end of main

} //end of class

output

1
2
3
1 2
1 3
2 1
2 3
3 1
3 2
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

A minor quibble, easy to correct: OP included the empty set in the outputs of the sought-for function. — High Performance Mark, Jun 30 '15 at 05:46
@HighPerformanceMark, instead of `for(int i=1;i<=a.length;i++)f(0,i,new ArrayDeque());` he may wrote `for(int i=0;i<=a.length;i++)`. Even simpler just to add empty list manually to any output. — , Jun 30 '15 at 06:06

score 0 · Answer 2 · answered Jun 29 '15 at 20:30

0

So what you are looking for is all the possible permutations of the Power Set.

This seems to go into some depth about strategies for doing this.

answered Jun 29 '15 at 20:30

Bnannerz

93
1
4

score 0 · Answer 3 · answered Jun 29 '15 at 20:32

If your list in N elements long, you want to get all the combinations of N taken by M, where M is between 1 and N. For each of the combination you want to get all the permutations. You can probably figure out algorithms for combinations and permutations via google.

score 0 · Accepted Answer · answered Jun 30 '15 at 20:43

I ended up using a combination of these two functions. Not sure if it works as intended, but so far it has been working properly.

// Generates all permutations of a set. Thus, given an input like [1, 2, 3] it changes the null
// final_list input to be [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
static void heappermute(List<List<Integer>> waypoints, int n,     List<List<List<Integer>>> final_list) {
    int i;
    if (n == 1) {
        final_list.add(waypoints);
    }
    else {
        for (i = 0; i < n; i++) {
            heappermute(waypoints, n-1, final_list);
            if (n % 2 == 1) {
                swap(waypoints.get(0), waypoints.get(n-1));
        }
            else {
                swap(waypoints.get(i), waypoints.get(n-1));
            }
        }
    }
}

static void swap (List<Integer> x, List<Integer> y)
{
    List<Integer> temp = new ArrayList<>();
    temp = x;
    x = y;
    y = temp;
}


// Generates all subsets of a given set. Thus, given a list of waypoints, it will return a list of 
// waypoint lists, each of which is a subset of the original list of waypoints.
// Ex: Input originalSet = {1, 2, 3}
//     Output: = {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}
// Code modified from http://stackoverflow.com/questions/4640034/calculating-all-of-the-subsets-of-a-set-of-numbers 

public static List<List<List<Integer>>> powerSet(List<List<Integer>> originalSet) {
    List<List<List<Integer>>> sets = new ArrayList<>();
    if (originalSet.isEmpty()) {
        sets.add(new ArrayList<List<Integer>>());
        return sets;
    }
    List<List<Integer>> list = new ArrayList<List<Integer>>(originalSet);
    List<Integer> head = list.get(0);
    List<List<Integer>> rest = new ArrayList<List<Integer>>(list.subList(1, list.size()));
    for (List<List<Integer>> set : powerSet(rest)) {
        List<List<Integer>> newSet = new ArrayList<List<Integer>>();
        newSet.add(head);
        newSet.addAll(set);
        sets.add(newSet);
        sets.add(set);
    }
    return sets;
}

Getting ALL permutations of ALL sublists of a list of integers

4 Answers4

Linked