Существует ли нерекурсивное решение для получения списка всех возможных конкатенаций массива строк?

Question

Я получаю в качестве входных данных массив строк.
Мне нужно создать список строк, представляющих собой конкатенацию всех строк входного массива, появляющихся один раз и только один раз для каждой строки.
Для Например, если входной массив равен ["aa","bb","cc"], результирующий список строк будет иметь вид "aabbcc",aaccbb","bbaacc","bbccaa",ccaabb","ccbbaa"
Длина входного массива неизвестна, это может быть любое число.
Длина всех подстрок в массиве то же самое.
Я вижу это Java: получить все объединения Списка вопрос.
Но есть ли нерекурсивное решение для этого?

Answer 1

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

Вы можете просто заменить int[] на String[].

Полный интерактивный пример:

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

Выходы:

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]

Чтобы изменить формат вывода, вы можете использовать:

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

формат вывода:

aaaaaa
bbaaaa
ccaaaa
aabbaa
...

Пожалуйста, посмотрите на ссылку topi c, чтобы найти объяснение, как она работает.