Создание различных перестановок из списков в Java

Question

Okay,

Мне нужна помощь в выяснении того, как я могу это сделать.

У меня есть основной список вложенных списков А - п объектов 1 - я, как показано ниже:

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

То, что я хочу от этого, список всех различных перестановок, но Я заранее не знаю, сколько элементов находится в дополнительных списках или сколько объектов в них.

Итак, объекты 1 - у меня есть атрибут в них, который я не хочу перекрывать. И мне нужен список всех возможных перестановок. Один объект из каждого под-списка. 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}} 

Я пытался придумать рекурсивный способ сделать это в Java, но я не уверен, как понять это, так как я не знаю, счетчики любого из списков, и они могут изменять каждый раз, когда это выполняется.

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

Вот очень простой итеративный подход: представить каждую перестановку как массив p из K целых чисел, представляющих индексы в списки A .. n. Каждый из элементов Kp[k] имеет диапазон от нуля до S[k]-1 включительно, где S[k] - это длина списка k.

Учитывая перестановку р _я, вы можете построить перестановки р _{я + 1} от «приращением» ваш массив таким же образом, что вы бы возрастать после целое число, если каждый p[k] были «цифра»:

• Начнет с всей-нулями перестановки
• на каждой итерации увеличивает перестановку приращения p[0]
• Если p[0] меньше S[0], выполняется инкремент; продолжает следующую перестановку
• В противном случае, установите p[0] к нулю, и приращение p[1]
• Если p[1] меньше S[1], инкрементация делается; продолжает следующую перестановку
• В противном случае, установите p[1] к нулю, и приращения p[2]
• Продолжайте, пока не дойдет до последнего индекса p[K-1]
• Если вы установите p[K-1] к нулю, вы сделали с петлей.

Учитывая массив индексов, тривиально построить перестановку фактических элементов списка. Обратите внимание, что количество перестановок может быть очень большим, поэтому будьте осторожны, сохраняя их в памяти.