Permutation of N lists

Question

i need all permutation from N lists, i dont know N until the program start, here is my SSCCE (i have implemented algorithm which was adviced to me, but it has some bugs).

First , create Place class:

public class Place {
public List<Integer> tokens ;

//constructor
public Place() {

  this.tokens = new ArrayList<Integer>();  
}

}

And then testing class:

public class TestyParmutace {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here

        List<Place> places = new ArrayList<Place>();

        Place place1 = new Place();
        place1.tokens.add(1);
        place1.tokens.add(2);
        place1.tokens.add(3);
        places.add(place1); //add place to the list

        Place place2 = new Place();
        place2.tokens.add(3);
        place2.tokens.add(4);
        place2.tokens.add(5);
        places.add(place2); //add place to the list

        Place place3 = new Place();
        place3.tokens.add(6);
        place3.tokens.add(7);
        place3.tokens.add(8);
        places.add(place3); //add place to the list


        //so we have
        //P1 = {1,2,3}
        //P2 = {3,4,5}
        //P3 = {6,7,8}


        List<Integer> tokens = new ArrayList<Integer>();

        Func(places,0,tokens);

    }

    /**
     * 
     * @param places list of places
     * @param index index of current place
     * @param tokens list of tokens
     * @return true if we passed guard, false if we did not
     */


    public static boolean Func( List<Place> places, int index, List<Integer> tokens) 

    {

        if (index >= places.size())
            {

                // if control reaches here, it means that we've recursed through a particular combination
                // ( consisting of exactly 1 token from each place ), and there are no more "places" left



                String outputTokens = "";
                for (int i = 0; i< tokens.size(); i++) {

                    outputTokens+= tokens.get(i) +",";
                }
                System.out.println("Tokens: "+outputTokens);

                if (tokens.get(0) == 4 && tokens.get(1) == 5 && tokens.get(2) == 10) {
                    System.out.println("we passed the guard with 3,5,8");
                    return true;
                }

                else {
                    tokens.remove(tokens.get(tokens.size()-1));
                    return false;
                }

            }

        Place p = places.get(index);

        for (int i = 0; i< p.tokens.size(); i++)
            {

                tokens.add(p.tokens.get(i));
                //System.out.println("Pridali sme token:" + p.tokens.get(i));

                if ( Func( places, index+1, tokens ) ) return true;

            }
        if (tokens.size()>0)
            tokens.remove(tokens.get(0));

        return false;

    }
}

and here is the output of this code:

Tokens: 1,3,6,
Tokens: 1,3,7,
Tokens: 1,3,8,
Tokens: 3,4,6,
Tokens: 3,4,7,
Tokens: 3,4,8,
Tokens: 4,5,6,
Tokens: 4,5,7,
Tokens: 4,5,8,
Tokens: 2,3,6,
Tokens: 2,3,7,
Tokens: 2,3,8,
Tokens: 3,4,6,
Tokens: 3,4,7,
Tokens: 3,4,8,
Tokens: 4,5,6,
Tokens: 4,5,7,
Tokens: 4,5,8,
Tokens: 3,3,6,
Tokens: 3,3,7,
Tokens: 3,3,8,
Tokens: 3,4,6,
Tokens: 3,4,7,
Tokens: 3,4,8,
Tokens: 4,5,6,
Tokens: 4,5,7,
Tokens: 4,5,8,

So, you see, some combinations are correct (1,3,6), some are incorrect (4,5,8) and some are completely missing (2,4,8,..) how to solve this problem ? number of places and also number of tokens in places can vary, i just used 3 places since with 2 places its working, but with more places it is buggy. Thanks.

why is (4,5,8) incorrect an (2,4,8) correct. Each has to be from a different list?? — UmNyobe, Apr 08 '12 at 11:04
yeah, exactly like you said. every token has to be from different list. — Anton Giertli, Apr 08 '12 at 11:20
This task is from more complex program - petri net editor/simulator, all transition can have guard - a condition that must be true if this transition is going to be executed... and to success this guard, i need to take all input places, and try all combinations of their token to pass this guard. place has list of tokens, and number of input places is variable..thats why i need combination from N lists. — Anton Giertli, Apr 08 '12 at 11:30
@PovedzHeslo I think you need to get all possible permutations first. And then filter them and left those, which passes guard. Do it in 2 different methods. — Mikita Belahlazau, Apr 08 '12 at 11:42

Mikita Belahlazau · Accepted Answer · 2013-04-18T21:49:37.867

You algorithm is almost correct. I think you don't need to return true or false and stop current iteration when you get true. I modified your method Func:

public static void Func( List<Place> places, int index, Deque<Integer> tokens) {
    if (index == places.size()) {
        // if control reaches here, it means that we've recursed through a particular combination
        // ( consisting of exactly 1 token from each place ), and there are no more "places" left
        String outputTokens = "";
        for (int token : tokens) {
            outputTokens += token + ",";
        }
        System.out.println("Tokens: "+outputTokens);
    } else {
        Place p = places.get(index);
        for (int token : p.tokens) {
            tokens.addLast(token);
            Func(places, index+1, tokens);
            token.removeLast();
        }
    }
}

I used Deque because it offers handy removeLast method to remove last added token. You can pass LinkedList as implementation of Deque.

Update

List<List<Integer>> combinations;

// Instead of printing result:
List<Integer> copy = new ArrayList<Integer>(tokens);
combinations.add(copy);

Hi, do you have any idea how to save the token combination ?i tried to use list of deque of integers, but whenever i add token combination to final list, it stili remains empty, since i call token.removeLast() afterwards, and it seems like that final lists contains just refference. — Anton Giertli, Apr 10 '12 at 11:37

score 0 · Answer 2 · edited May 23 '17 at 12:04

0

You are trying to do set cross products, not really permutations. So you need to do

 for(Integer token1 : place1.tokens){
    for(Integer token2 : place2.tokens){
       for(Integer token3 : place3.tokens){
            //crossValue = (token1, token2, token3);
        }
    }
 }

Now if you want to have all permutations, for example for [1,3,6,] also have [1,6,3], [3,6,1], etcc.. you need a function which output permutations given a list or array, see Permutation of array

edited May 23 '17 at 12:04

Community

1
1

answered Apr 08 '12 at 11:33

UmNyobe

22,539
9
61
90

1

but you forgot that the number of places is N, not 3. – Anton Giertli Apr 08 '12 at 11:46
Yes, I viewed this question because I have legacy code with these hard-coded loops that need to be updated to a dynamic algorithm. – Nate Glenn Dec 19 '14 at 14:42

Permutation of N lists

2 Answers2

Linked