generate ALL possible combinations from a number of lists

Question

Salam, I want to get list of combinations that represents every unique combination of all values in my list of lists. for example, have a list that containes a list of Sessions and i want a combination from each list of sessions:

My List of lists 
     {   List of Sessions1[S1,S2,S3]
         List of Sessions2[S4,S5]
         List of Sessions3[S6,S7]
     }

the List i get is

   List result
              {
               List combination 1[S1,S4,S6]
              List combination 2[S1,S4,S7]
           List combination 3[S1,S5,S6]
    .
    .
    .
}

I have a method and it works but the problem is with the variable j cause my lists are too big so when it passes 9223372036854775807 (2^63-1) it starts giving negative values and it ruins the progress here's my code

 public List<List<Seance>> allUniqueCombinations1(List<List<Seance>> dataStructure) throws SQLException {
        int n = dataStructure.size();
        long solutions = 1;
        for (List vector : dataStructure) {
            solutions *= vector.size(); if(solutions>1000000000) break;//this condition is for the same problem
        }
        List<List<Seance>> allCombinations = new LinkedList();     

        for (int i = 0; i < solutions; i++) {
         List<List<List<Seance>>> liste = new LinkedList();        
              List<Seance> combination = new LinkedList();
                 long j = 1;
               List<List<Seance>> data = new LinkedList();
                data = dataStructure;                
                int u = 0;
                for (int a=0;a< data.size();a++) {
                   List vec =(List<Seance>) data.get(a);

                    combination.add((Seance) vec.get((i / (int)j) % vec.size()));
                    j *= vec.size();
  data = remouve_conflicts(data, combination.get(u),u);//this removes all the sessions that will make a conflict with the session chosen in order not to appear in my combinition
                    u++;

                }  

            }


        return allCombinations;
    }

https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html — Mitch, Apr 04 '20 at 17:51
`BigInteger solutions = new BigInteger("1")` instead of `long` — Abra, Apr 04 '20 at 17:57

score 0 · Answer 1 · answered Apr 04 '20 at 18:04

The limit for Long is Long.MAX_VALUE which equates to 9,223,372,036,854,775,807. On passing that value, it wraps around to Long.MIN_VALUE which equates to -9,223,372,036,854,775,808.

That is, Integer.MAX_VALUE + 1 == Integer.MIN_VALUE, which is what you're experiencing.

Use the datatype BigInt, which should suit your purpose; in theory it has no upper bound, and is practically bound by your available memory(which is a lot for a variable).

score 0 · Accepted Answer · edited Apr 04 '20 at 21:11

If I understand your requirements correctly you don't have to pre-calculate the number of permutations. Instead you can use the "odometer" approach, keeping an array of indexes into your list of input lists, and incrementing the "odometer" at each iteration.

List<List<String>> input = new ArrayList<>();
input.add(Arrays.asList(new String[] {"S1", "S2", "S3"}));
input.add(Arrays.asList(new String[] {"S4", "S5"}));
input.add(Arrays.asList(new String[] {"S6", "S7"}));

int[] idx = new int[input.size()];

List<String> base  = new ArrayList<>();
for(List<String> sl : input) base.add(sl.get(0));

List<List<String>> allCombinations  = new ArrayList<>();

while(true)
{
  allCombinations.add(new ArrayList<>(base));

  int k=idx.length-1;
  for(; k>=0; k--)
  {
    idx[k] += 1;
    if(idx[k] < input.get(k).size()) 
    {
      base.set(k, input.get(k).get(idx[k]));
      break;
    }
    idx[k] = 0;
    base.set(k, input.get(k).get(idx[k]));
  }
  if(k < 0) break;          
}

for(List<String> combo : allCombinations)
    System.out.println(combo);

Output:

[S1, S4, S6]
[S1, S4, S7]
[S1, S5, S6]
[S1, S5, S7]
[S2, S4, S6]
[S2, S4, S7]
[S2, S5, S6]
[S2, S5, S7]
[S3, S4, S6]
[S3, S4, S7]
[S3, S5, S6]
[S3, S5, S7]

but like this how can i minimise the complexity of algorithm cz i have a very big list.. for example i don't want S1 with S4 so i avoid all combination that gother S1 with S4 — Meriem, Apr 05 '20 at 10:08

generate ALL possible combinations from a number of lists

2 Answers2