Creating different permutations from lists in Java

Question

Okay,

I need some help figuring out how I can do this.

I have a Main List of sub-lists A - n of objects 1 - i as shown below:

M{A(1, 2, 3, ... i),
B(1, 2, 3, ... i),
C(1, 2, 3, ... i), ... ,
n(1, 2, 3, ... i)}

What I want from this, is a list of all the different permutations of this, but I do not know ahead of time how many items are in the sub lists, or how many objects are in those.

So the objects 1 - i have an attribute in them that I do not want to overlap. And I need a list of all the possible permutations. One object from each sub-list. EX:

All{
1{A.1, B.1, C.1 N.1},
2{A.1, B.1, C.1 N.2},
3{A.1, B.1, C.1 N.3},
...
{A.1, B.1, C.1 N.i},
{A.1, B.1, C.2 N.1},
{A.1, B.1, C.2 N.2},
{A.1, B.1, C.2 N.3},
...
{A.1, B.1, C.2 N.i},
{A.1, B.2, C.1 N.1},
{A.1, B.2, C.1 N.2},
{A.1, B.2, C.1 N.3},
...
{A.1, B.2, C.1 N.i},
...
...
...
{A.i, B.i, C.i N.i}}

I have been trying to think of a recursive way to do this in Java, but am not sure how to figure it out since I do not know the counts of any of the lists, and they can change each time that this is ran.

Answer 1

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;


public class Main
{
    private static String [][] inputList = 
    {
        {"A1","A2","A3","A4"},
        {"B1","B2","B3","B4"},
        {"C1","C2","C3","C4"},
    };
    private static int listSize = 4;
    private static List<List<String>> lists = new ArrayList<List<String>>();

    public static void permutation(List<Integer> indexes, int size)
    {
        if(checkEnd(indexes, size))
        {
            return;
        }
        List<String> nextList = new ArrayList<String>();
        int rowIndex = 0;
        for(int i : indexes)
        {
            nextList.add(inputList[rowIndex++][i]);
        }
        lists.add(nextList);
        permutation(nextIndexes(indexes, size),size);
    }

    public static boolean checkEnd(List<Integer> indexes, int size)
    {
        for(int i : indexes)
        {
            if(i < (size - 1))
            {
                return false;
            }
        }
        return true;
    }

    public static List<Integer> nextIndexes(List<Integer> indexes, int size)
    {
        Collections.reverse(indexes);
        for(int index = 0; index < indexes.size(); index++)
        {
            if(indexes.get(index) < (size - 1))
            {
                indexes.set(index, indexes.get(index) + 1);
                break;
            }
        } 
        Collections.reverse(indexes);
        return indexes;
    }

    public static void printList(List<String> list)
    {
        StringBuilder builder = new StringBuilder();
        builder.append("{");
        for(String field : list)
        {
            builder.append(field);
            builder.append(",");
        }
        builder.deleteCharAt(builder.length()-1);
        builder.append("}");
        System.out.println(builder.toString());
    }

    public static void main(String[] args)
    {
        List<Integer> indexes = new ArrayList<Integer>();
        for(int i = 0; i < inputList.length; i++)
        {
            indexes.add(0);
        }
        permutation(indexes, listSize);
        for(List<String> list : lists)
        {
            printList(list);
        }
    }
}

Answer 2

Here is a very simple iterative approach: represent each permutation as an array p of K integers representing indexes into lists A..n. Each of the K elements p[k] has a range from zero to S[k]-1, inclusive, where S[k] is the length of list k.

Given a permutation p_i, you can construct permutation p_i+1 by "incrementing" your array in the same way that you would increment an integer number if each p[k] were a "digit":

• Start with an all-zeros permutation
• On each iteration, increment the permutation by incrementing p[0]
• If p[0] is less than S[0], incrementing is done; continue to next permutation
• Otherwise, set p[0] to zero, and increment p[1]
• If p[1] is less than S[1], incrementing is done; continue to next permutation
• Otherwise, set p[1] to zero, and increment p[2]
• Continue until you reach the last index p[K-1]
• If you set p[K-1] to zero, you are done with the loop.

Given an array of indexes it is trivial to construct a permutation of actual list elements. Note that the number of permutations can get pretty large very fast, so be very careful storing them in memory.