Create multiple arrays from a given string array

Question

I have an array of unique strings from which i need to create all possible arrays with the same length.

String[] str = {"Belgium", "France", "Germany"};

The goal is to create a list of arrays which have every possible value from above array at each index,

[Belgium, Belgium, Belgium]
[Belgium, Belgium, France]
[Belgium, Belgium, Germany]
[Belgium, France, Belgium]
[Belgium, France, France]
[Belgium, France, Germany]
[Belgium, Germany, Belgium]
[Belgium, Germany, France]
[Belgium, Germany, Germany]
[France, Belgium, Belgium]

....

[Germany, Germany, France]
[Germany, Germany, Germany]

My code to create this looks like

static List<String[]> getAllAllocations(String[] input){
    List<String[]> result = new ArrayList<>();
    if(input.length == 2){
        for(int i = 0; i < 2; i++){
            for(int j = 0; j < 2; j++){
                result.add(new String[]{input[i], input[j]});
            } 
        }
    }
    else if(input.length == 3){
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                for(int k = 0; k < 3; k++){
                    result.add(new String[]{input[i], input[j], input[k]});
                }
            } 
        }
    }
    else if(input.length == 4){
        for(int i = 0; i < 4; i++){
            for(int j = 0; j < 4; j++){
                for(int k = 0; k < 4; k++){
                    for(int m = 0; m < 4; m++){
                        result.add(new String[]{input[i], input[j], input[k], input[m]});
                    }
                }
            } 
        }
    }
    //else if(input.length == 5) similar code with 5 for loops
    //else if(input.length == 6) similar code with 6 for loops
    //else if(input.length == 7) similar code with 7 for loops
    //else if(input.length == 8) similar code with 8 for loops
    return result;
}

The array will have a variable length between 2 and 8. How can I dynamicaly create the for loops instead of chaining the if-else checks or any other way to do this in an elganter way than I did above?

@Rocco I have tried recursion, but it was difficult and I had problems to add a string to an existing array. I would appreciate a little more input how to solve this using recursion — Biscuit
– Biscuit, Commented Apr 20, 2021 at 15:24

Rocco · Accepted Answer · 2021-04-20 15:59:23Z

4

Recursive solution

public static List<String[]> getAllAllocations(String[] input) {
    List<String[]> result=new ArrayList<String[]>();
    getAllAllocations(result, input, new String[input.length], 0);
    return result;
}

public static void getAllAllocations(List<String[]> result, String[] input, String[] current, int depth) {
    if (depth>=input.length) {
        result.add(current.clone());
    } else {
        for (int i=0;i<input.length;i++) {
            current[depth]=input[i];
            getAllAllocations(result, input, current, depth+1);
        }
    }
}

Iterative solution

public static List<String[]> getAllAllocations2(String[] input) {
    List<String[]> result=new ArrayList<String[]>();
    
    int[] counters=new int[input.length];
    
    boolean done=false;
    while (!done) {
        
        String[] comb=new String[input.length];
        for (int i=0;i<comb.length;i++) {
            comb[i]=input[counters[i]];
        }
        result.add(comb);

        done=true;
        for (int i=0;i<counters.length;i++) {
            counters[i]++;
            if (counters[i]>=input.length) {
                counters[i]=0;
            } else {
                done=false;
                break;
            }
        }
    }
    
    return result;
}

edited Apr 20, 2021 at 15:59

answered Apr 20, 2021 at 15:31

Rocco

1,1187 silver badges11 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Biscuit Over a year ago

Thank you very much. i didn't fully understand what is going on, specially in the second method but tested it with different inputs and this works as desired. Thank you again.

Rocco Over a year ago

@Biscuit the second method is recursively generating the combinations, by rotating the input elements in the current array. Each level of recursion is responsible of rotating the depth-th element of array, when the last level is reached the combination is complete and added to the result. Since the current array is mutable it must be cloned to avoid side effect on the result.

Rocco Over a year ago

@Biscuit I also added an iterative solution, but in my opinion it's even more obscure of recursion in this case

Tim Tong Over a year ago

The specific term for what Rocco is using in the recursive approach is called backtracking. It's an algorithm generally used for combination/permutation based problems. Check out this article -- geeksforgeeks.org/backtracking-introduction

Biscuit Over a year ago

I think I'm beginning to understand how it works. Thanks again for the other approach Rocco and the link @Tim Tong

score 0 · Accepted Answer · 2021-05-29 08:36:20Z

You can use map and reduce approach:

map - first prepare the lists of arrays List<String[]>. An array of three elements becomes three lists of singleton arrays:

list1: [[Belgium], [France], [Germany]]
list2: [[Belgium], [France], [Germany]]
list3: [[Belgium], [France], [Germany]]

reduce - then multiply these lists sequentially one by one and get the Cartesian product. Two steps of reduction for three lists:

list1: [[Belgium], [France], [Germany]]
list2: [[Belgium], [France], [Germany]]
------
 sum1: [[Belgium, Belgium], [Belgium, France], ..., [Germany, Germany]]

 sum1: [[Belgium, Belgium], [Belgium, France], ..., [Germany, Germany]]
list3: [[Belgium], [France], [Germany]]
------
total: [[Belgium, Belgium, Belgium], [Belgium, Belgium, France], ...]

Try it online!

public static void main(String[] args) {
    String[] str = {"Belgium", "France", "Germany"};
    cartesianProduct(str).forEach(arr->System.out.println(Arrays.toString(arr)));
}

static List<String[]> cartesianProduct(String[] input) {
    return IntStream.range(0, input.length)
            // Stream<List<String[]>>
            .mapToObj(i -> Arrays.stream(input)
                    .map(str -> new String[]{str})
                    .collect(Collectors.toList()))
            // stream of lists to a single list
            .reduce((list1, list2) -> list1.stream()
                    .flatMap(arr1 -> list2.stream()
                            .map(arr2 -> Stream.of(arr1, arr2)
                                    .flatMap(Arrays::stream)
                                    .toArray(String[]::new)))
                    .collect(Collectors.toList()))
            .orElse(Collections.emptyList());
}

Collectives™ on Stack Overflow

Create multiple arrays from a given string array

2 Answers 2

5 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related