Is there a non-recursive solution to get a list of all possible concatenations of array of strings?

Question

I receive as an input an array of strings.
I have to create a list of strings that are a concatenation of all the strings of the input array, appearing once and only once for each string.
For example if the input array is ["aa","bb","cc"] the resulting list of strings will be "aabbcc",aaccbb","bbaacc","bbccaa",ccaabb","ccbbaa"
The length of the input array is not known, it can be any number.
The length of all the substrings in the array is the same.
I see this Java: get all concatenations of List<List<String>> question.
But are there any non-recursive solution for this?

Any solution that can be written with recursion can be written without. If you know of a recursive solution, you can adapt it to use an imperative loop by adding a `Stack` object to emulate the call stack that recursion makes use of. It might not (actually, definitely won't) be as pretty as the recursive way, but it'll work. — Carcigenicate, Feb 16 '20 at 17:13
As a note, that would just emulate recursion. Most people would consider something like that still recursive, as the approach itself is still recursive. — Zabuzard, Feb 16 '20 at 17:39
Please see: [Why is “Is it possible to…” a poorly worded question?](https://softwareengineering.meta.stackexchange.com/q/7273). — Progman, Feb 16 '20 at 17:47

Stefan · Answer 1 · 2020-02-16T21:25:18.473

I just wrote an example which does the same with integer numbers: Get all combinations for arbitrary number of elements

You can simply replace int[] by String[] there.

A complete interactive example:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

class Main
{

    /**
     * Return all possible combination of n Strings
     * @param n Number of parts to combine in each row
     * @param set Array of Strings to combine
     */
    static List<String[]> getAll(int n, String[] set)
    {
        List<String[]> combinations = new ArrayList<>();

        // First step (0)
        // Create initial combinations, filled with the first String.
        for (int number = 0; number < set.length; number++)
        {
            String[] array = new String[n]; // the final size of each array is already known
            array[0] = set[number]; // fill the first Part
            combinations.add(array);
        }

        // In each following step, we add one number to each combination
        for (int step = 1; step < n; step++)
        {
            // Backup the size because we do not want to process
            // the new items that are added by the following loop itself.
            int size = combinations.size();

            // Add one number to the existing combinations
            for (int combination = 0; combination < size; combination++)
            {
                // Add one part to the existing array
                String[] array = combinations.get(combination);
                array[step] = set[0];

                // For all additional Strings, create a copy of the array
                for (int number = 1; number < set.length; number++)
                {
                    String[] copy = Arrays.copyOf(array, array.length);
                    copy[step] = set[number];
                    combinations.add(copy);
                }
            }
        }

        return combinations;
    }

    public static void main(String[] args)
    {
        System.out.println("Enter some Strings, delimited by space");
        Scanner in=new Scanner(System.in);
        String line=in.nextLine();
        String[] set=line.split("\\s+");

        // Calculate all possible combinations
        List<String[]> combinations = getAll(set.length, set);

        // Print the result
        for (String[] combination : combinations)
        {
            System.out.println(Arrays.toString(combination));
        }
    }
}

Outputs:

Enter some Strings, delimited by space
aa bb cc
[aa, aa, aa]
[bb, aa, aa]
[cc, aa, aa]
[aa, bb, aa]
[aa, cc, aa]
[bb, bb, aa]
[bb, cc, aa]
[cc, bb, aa]
[cc, cc, aa]
[aa, aa, bb]
[aa, aa, cc]
[bb, aa, bb]
[bb, aa, cc]
[cc, aa, bb]
[cc, aa, cc]
[aa, bb, bb]
[aa, bb, cc]
[aa, cc, bb]
[aa, cc, cc]
[bb, bb, bb]
[bb, bb, cc]
[bb, cc, bb]
[bb, cc, cc]
[cc, bb, bb]
[cc, bb, cc]
[cc, cc, bb]
[cc, cc, cc]

To change the output format, you may use:

        // Print the result
        for (String[] combination : combinations)
        {
            String s=String.join("",combination); // Concatenate the parts of each combination
            System.out.println(s);
        }

The the output format is:

aaaaaa
bbaaaa
ccaaaa
aabbaa
...

Please take a look at the linked topic to find the explanation how it works.

Thank you for an answer, but here the number of strings in the array is now known in advance. I mean it is a parameter that changes from run to run. So I can not use a hardcoded `n` `for` loops as you have in your code. — Prophet, Feb 16 '20 at 20:55
You can of course fill the input parameters dynamically. There is no need to have them hard coded. This is just a simple example which focuses on the algorithm rather than on input ad output. — Stefan, Feb 16 '20 at 21:17
You read in your input file become you pass it to the getAll method. By that time you should know the length. — NomadMaker, Feb 17 '20 at 00:54
I asked for all the combinations where each word appears only once... But thank you for the way of thought — Prophet, Feb 17 '20 at 15:06
"where each word appears only once" I missed that requirement. In this case you add a filter to the loop "for (int combination...." which prevents the wrong entries. — Stefan, Feb 17 '20 at 15:10

Is there a non-recursive solution to get a list of all possible concatenations of array of strings?

1 Answers1