CODEWITHSUNDEEP
algorithmsetcombinations
jj172
jj172

Reputation: 809

Getting ALL permutations of ALL sublists of a list of integers

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!

Upvotes: 1

Views: 1926

Answers (4)

jj172
jj172

Reputation: 809

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

Upvotes: 0

user2104560
user2104560

Reputation: 

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

Upvotes: 2

Mircea
Mircea

Reputation: 10566

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.

Upvotes: 0

Bnannerz
Bnannerz

Reputation: 93

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.

Upvotes: 0

Related Questions