генерировать ВСЕ возможные комбинации из ряда списков - PullRequest
Новая
       18

генерировать ВСЕ возможные комбинации из ряда списков

0 голосов
/ 04 апреля 2020

Салам, я хочу получить список комбинаций, который представляет каждую уникальную комбинацию всех значений в моем списке списков. например, у меня есть список, который содержит список сессий, и я хочу комбинацию из каждого списка сессий: 

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

Ответы [ 2 ]

0 голосов
/ 04 апреля 2020

Если я правильно понимаю ваши требования, вам не нужно предварительно рассчитывать количество перестановок. Вместо этого вы можете использовать подход «одометр», сохраняя массив индексов в списке входных списков и увеличивая «одометр» на каждой итерации. 

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]
0 голосов
/ 04 апреля 2020

Предел для 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, который соответствует вашим целям; в теории он не имеет верхней границы и практически связан с вашей доступной памятью (что очень много для переменной).

...