How to generate a list of arrays (all have the length M) with N possible elements (M > N) in Java?

Question

For example, if elements are {1, 2} (n = 2) and m = 3, the method should generate a list of arrays like this {[1,1,1],[1,1,2],[1,2,1],[2,1,1],[1,2,2],[2,2,1],[2,1,2],[2,2,2]}.

I know Python can do things like y = itertools.product((1, 2), repeat=3), but how do I implement this in Java efficiently. I have tried feed some initial List and used the following to get what I wanted but the time complexity is too high and performance is extremely bad when the input is big.

public static List<List<Integer>> permute (List<Integer> list, int need) {

    List<List<Integer>> result = new ArrayList<>();
    if (need--==0) {
        result.add(list);
        return result;
    }
    for (int current : list)
        insert(permute(list,need), current, result);
    return result;
}


private static void insert(List<List<Integer>> currentLists, int currentInt, List<List<Integer>> list) {
    for (List<Integer> currentList : currentLists) {
        int size = currentList.size();
        for (int i = 0; i <= size; i++) {
            List<Integer> newList = new LinkedList<>();
            newList.addAll(currentList);
            newList.add(i, currentInt);
            list.add(newList);
        }
    }
}

Answer 1

Using libary StreamEx solution could look like:

    List<Integer> list = Arrays.asList(1, 2);
    int need = 3;
    StreamEx<List<Integer>> product = StreamEx.cartesianPower(need, list);

you could gain efficiency using parallel processing or by consuming only part of lazily generated result.

---

Another lazy solution in plain old java would create Iterator that produce permutations lazily

class Permutator<T> implements Iterable<List<T>> {

    final List<T> items;
    final int homMuch;

    Permutator(List<T> items, int homMuch) {
        this.items = items;
        this.homMuch = homMuch;
    }

    @Override
    public Iterator<List<T>> iterator() {
        return new Iterator<List<T>>() {
            static final int OVERFLOW = -1;
            final int[] permutation = new int[homMuch];
            final int max = items.size();

            @Override
            public boolean hasNext() {
                for (int item : permutation) {
                    if (item == OVERFLOW) {
                        return false;
                    }
                }
                return true;
            }

            @Override
            public List<T> next() {
                ArrayList<T> result = new ArrayList<>(permutation.length);
                for (int index : permutation) {
                    result.add(items.get(index));
                }

                inc(permutation, 0);           // generate next permutation

                return result;
            }

            private void inc(int[] indexes, int index) {
                if (index >= indexes.length) {
                    for (int i = 0; i < indexes.length; i++) {
                        indexes[i] = OVERFLOW;
                    }
                    return;
                }
                int nextValue = indexes[index] + 1;
                if (nextValue < max) {
                    indexes[index] = nextValue;
                } else {
                    indexes[index] = 0;
                    inc(indexes, index + 1);
                }
            }

        };
    }
}

such generator can be used lazily in loops

List<String> list = Arrays.asList("one", "two");
int need = 3;
for (List<String> permutation : new Permutator<>(list, need)) {
    System.out.println(permutation);
}

Output:

[one, one, one]
[two, one, one]
[one, two, one]
[two, two, one]
[one, one, two]
[two, one, two]
[one, two, two]
[two, two, two]

Answer 2

Here is a way to do it. I initialize the rows. Then I fill each row by column. There is a little trickiness getting it to iterate on the right, but nothing too hard.

public class GeneratePermutations {

  public static void main(String[] args) {
      int[] inputs = {1, 2, 3};
      List<int[]> results = permute(inputs, 4);
      printResults(results);
  }

  private static List<int[]> permute(int[] inputs, int size) {
      // set up the rows
      List<int[]> results = new ArrayList<int[]>();
      int count = (int)Math.pow(inputs.length, size);
      for (int row = 0; row < count; row++) {
          results.add(new int[size]);
      }

      // fill the rows by column
      for (int column = 0; column < size; column++) {
          permute(results, inputs, column);
      }

      return results;
  }

  private static void permute(List<int[]> results, int[] inputs, int column) {
      int inputIndex = 0;
        int input = inputs[inputIndex];

      // How often should we increment through the inputs?
      // If we use "column" as the exponent then we iterate more frequently
      // on the left (e.g. [1,1,1], [2,1,1], [1,2,1], etc.)
      // In order to iterate more right to left, use "size - column"
      // as the exponent.
      int incrIndex = 0;
      final int exponent = results.get(0).length - 1 - column;
      final int incrLength = (int)Math.pow(inputs.length, exponent);

      for (int[] result : results) {
          result[column] = input;

          // How often we step through the inputs depends on the column.
          incrIndex = (incrIndex + 1) % incrLength;
          if (incrIndex == 0) {
              inputIndex = (inputIndex + 1) % inputs.length;
              input = inputs[inputIndex];
          }
      }
  }

  private static void printResults(List<int[]> results) {
      for (int[] result : results) {
          System.out.println(Arrays.toString(result));
      }
  }
}

Answer 3

In fact you can't reduce the complexity. The minimum number of operations you have to do is the creation of your Lists. The number of lists can't be reduced (it's always equal to n^m) and the creation of these lists is the thing which takes a lot of time during the execution.

I added my code which I used to make some tests if it could help you.

//Main method who generate the resultList
public static ArrayList<ArrayList<Integer>> generateList(ArrayList<Integer> elements, int size) {
    //Initialisation
    ArrayList<ArrayList<Integer>> resultList = new ArrayList<ArrayList<Integer>>();
    ArrayList<Integer> indexes = new ArrayList<Integer>();

    for(int i = 0; i < size;i++){
       indexes.add(0);
    }


    resultList.add(generateCurrentList(indexes,elements)); //Add the first element

    for(int i = 0; i < Math.pow(elements.size(),size)-1;i++){ //Add the other elements by incrementing indexes at each add
        incrementIndexes(indexes,elements.size());
        resultList.add(generateCurrentList(indexes,elements));
    }

    return resultList;  
}


//Increment indexes
public static void incrementIndexes(ArrayList<Integer> indexes,int nbrElements){
    indexes.set(indexes.size()-1, indexes.get(indexes.size()-1)+1); //Increment the last index
    for(int i = indexes.size()-1;i > 0;i--){//For each index increment the previous one if the current is greater than the number of element
        if(indexes.get(i)==nbrElements)
            indexes.set(i-1, indexes.get(i-1)+1);
    }
    for(int i = 0;i < indexes.size();i++){
        indexes.set(i, indexes.get(i)%nbrElements);
    }
}

//Generate an arrayList using the current indexes and the list of elements
public static ArrayList<Integer> generateCurrentList(ArrayList<Integer> indexes,ArrayList<Integer> elements){
    ArrayList<Integer> currentList = new ArrayList<Integer>();
    for(int i = 0; i < indexes.size();i++){
        currentList.add(elements.get(indexes.get(i)));
    }
    return currentList;
}`