从多个列表中生成所有可能的组合

Question

萨拉姆，我想获得代表列表列表中所有值的每个唯一组合的组合列表。例如，有一个包含会话列表的列表，我想要每个会话列表的组合：

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

我得到的列表是

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

我有一个方法，它可以工作，但问题出在变量 j 上，因为我的列表太大，所以当它通过 9223372036854775807 (2^63-1) 时，它开始给出负值并破坏了进度这是我的代码

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

Answer 1

Long 的上限是 Long.MAX_VALUE，等于 9,223,372,036,854,775,807。在传递该值时，它环绕到 Long.MIN_VALUE，等于 -9,223,372,036,854,775,808。

也就是说，Integer.MAX_VALUE + 1 == Integer.MIN_VALUE，这就是您正在经历的。

使用适合您目的的数据类型BigInt；理论上它没有上限，实际上受可用内存的限制（这对于变量来说很大）。

Answer 2

如果我正确理解了您的要求，您就不必预先计算排列数。相反，您可以使用 "odometer" 方法，将索引数组保存到输入列表列表中，并在每次迭代时递增 "odometer"。

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

输出：

[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]

从多个列表中生成所有可能的组合

generate ALL possible combinations from a number of lists

java

algorithm

combinations

method-combination