Итеративно найдите все комбинации размера k массива символов (N выбирает K)

Вот еще одно итеративное решение:

Вы можете создать массив целых чисел размера K, чтобы действовать как счетчик, записывающий, как далеко вы прошли через комбинации, и массив символов для хранения текущей комбинации.

Напечатав каждую, переходим к следующей комбинации, увеличивая одно из значений счетчика, и если он «переполняется», достигая значения, равного количеству элементов в E, то сбрасывает его на ноль и выполняет перенос, увеличивая значение счетчика. счетчик в следующей позиции, проверка на переполнение там же и так далее. Что-то вроде одометра в автомобиле, за исключением того, что числа привязаны к значениям в E. Как только последняя позиция переполняется, вы сгенерировали все возможные комбинации.

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

Вам не нужно хранить массив символов с текущей комбинацией, вы можете просто перегенерировать его каждый раз в цикле for на основе счетчиков, но это может быть менее эффективно. Этот подход обновляет только те значения, которые изменяются.

public static void buildStrings(char[] root, int length)
{
    // allocate an int array to hold the counts:
    int[] pos = new int[length];
    // allocate a char array to hold the current combination:
    char[] combo = new char[length];
    // initialize to the first value:
    for(int i = 0; i < length; i++)
        combo[i] = root[0];

    while(true)
    {
        // output the current combination:
        System.out.println(String.valueOf(combo));

        // move on to the next combination:
        int place = length - 1;
        while(place >= 0)
        {
            if(++pos[place] == root.length)
            {
                // overflow, reset to zero
                pos[place] = 0;
                combo[place] = root[0];
                place--; // and carry across to the next value
            }
            else
            {
                // no overflow, just set the char value and we're done
                combo[place] = root[pos[place]];
                break;
            }
        }
        if(place < 0)
            break;  // overflowed the last position, no more combinations
    }
}

демонстрация ideone.com

Рекурсивное решение

Что касается меня, то здесь лучше всего подходит рекурсивное решение.
Вы можете заменить клонирование массива путей стеком для повышения производительности:

char[] pool = new char[]{'1', '2', '3'};
Stack<int> stack = new Stack<int>();

// Actually, resulting length should be the same length as pool array
int length = pool.length;

public void buildStringRec(int pos)
{
    if (length == pos + 1) 
    {
        System.out.println(String.valueOf(root));
        return;
    }

    for(char c : pool){
        stack.Push(c);
        buildStringRec(pos + 1);
        stack.Pop(c);
    }
}

Итеративное решение

Предположим, что по какой-то причине вам нужно сделать это итеративно.
Я уверен, что есть лучшее решение. Однако это лучшее, что я мог сделать.

Вы можете перефразировать свою задачу на другую:

Как вывести ВСЕ числа в базе N длины N.

Предположим, у вас есть массив длины 3: {'a', 1, 'z'}.
Желаемым ответом будет:

a-a-a    a-a-1    a-a-z
a-1-a    a-1-1    a-1-z
a-z-a    a-z-1    a-z-z
1-a-a    1-a-1    1-a-z

Теперь давайте посмотрим на индексы этих значений:

0-0-0    0-0-1    0-0-2
0-1-0    0-1-1    0-1-2
0-2-0    0-2-1    0-2-2 
2-0-0    2-0-1    2-0-2

На самом деле, это последовательные числа по основанию 3: 000, 001, 002, 010, 011, 012, 020, 021, 022, 200, 201, 202.

Запомните формулу их подсчета: base ^ length. В нашем случае length == base. Таким образом, это base ^ base.

Теперь наша задача упрощается:

int[] toBase(long bs, long value)
{ 
    int[] result = new int[bs];
    for (long i = bs - 1; i >= 0; i--)
    {
        result[i] = (int)(value % bs);
        value = value / bs;
    }
    return result;
}

long Pow(long a, long b)
{
    long result = 1;
    for (int i = 0; i < b; i++) result *= a;
    return result;
}

char[] pool = new char[] {'a', 'b', 'c'};

void outputAll()
{
    long n = pool.Length;
    for (long i = 0; i < Pow(n, n); i++)
    {
        int[] indices = toBase(n, i);
        for (int j = 0; j < n; j++)
            Console.Write("{0} ", pool[indices[j]]);
        Console.WriteLine();
    }
}

Конечно, могут быть некоторые оптимизации:

• Нет необходимости каждый раз вычислять toBase. Проще и производительнее начинать с 000 и каждый раз вычислять следующее число.
• Вы можете изменить функцию Pow, чтобы использовать быстрый алгоритм exponentiation by squaring и т. д.

Это всего лишь пример, поясняющий подход.

Имейте в виду, что массив длины 3 будет иметь всего 27 таких комбинаций. Однако массив длины 7 будет иметь 823543. Он растет экспоненциально.

Рабочий образец

Вот рабочая демонстрация DotNetFiddle.

Просто измените значения массива pool, чтобы получить результаты. Здесь и во всех приведенных выше примерах я использовал C#. Его можно легко преобразовать в C++ :)

Как по мне, он прекрасно работает до длины 7 (примерно 1-1,5 секунды).
Конечно, для получения таких результатов вам нужно будет убрать консольный вывод. Консольный вывод работает очень медленно.

Простым итеративным решением было бы

• создайте массив для хранения индекса для каждого символа для необходимой длины вывода
• Затем выполните итерацию по индексам и распечатайте каждый символ из пула, соответствующего индексам.
• Затем увеличьте последний индекс массива индексов
• if the last index is equal to the pool length
  • set it to zero
  • увеличить предыдущий индекс
  • повторяйте с предыдущим индексом, пока не достигнете начала массива или индекс не будет равен длине пула

Ниже приведен пример кода на Java.

char[] pool = new char[]{'1', '2', '3'};

public void buildStrings(int length){

  int[] indexes = new int[length];
  // In Java all values in new array are set to zero by default
  // in other languages you may have to loop through and set them.

  int pMax = pool.length;  // stored to speed calculation
  while (indexes[0] < pMax){ //if the first index is bigger then pMax we are done

    // print the current permutation
    for (int i = 0; i < length; i++){
      System.out.print(pool[indexes[i]]);//print each character
    }
    System.out.println(); //print end of line

    // increment indexes
    indexes[length-1]++; // increment the last index
    for (int i = length-1; indexes[i] == pMax && i > 0; i--){ // if increment overflows 
      indexes[i-1]++;  // increment previous index
      indexes[i]=0;   // set current index to zero  
    }     
  }
}

Итеративное решение

Вот алгоритм, который я разработал на C/C++, с итеративными функциями и постоянной пространственной сложностью.

Он обрабатывает индексы массива C, поэтому его можно использовать для любого типа данных, здесь массив символов (строка C++), который может быть строкой цифр.

Функция 1: генерировать все возможные комбинации

// str: string of characters or digits
void GenerateAll(string str, int k)
{
    int n = str.length();

    // initialization of the first subset containing k elements
    int *sub_tab = new int[k];
    for(int j(0); j<k; ++j)
    {
        sub_tab[j] = j;
    }

    do
    {   
        // Convert combination to string
        char *sub_str = new char[k];
        for(int j(0); j<k; ++j)
        {
            sub_str[j] = str[sub_tab[j]];
        }
        // Print combinations of each set
        Combinations(sub_str);
        // get next sub string
    } while (AddOne(sub_tab, k-1, n) == true);

    delete [] sub_tab;      
}

Функция 2: генерировать все комбинации для каждого набора

void Combinations(string str)
{
    int n = str.length();

    // Compute all factorials from 0 to n
    unsigned long int * factorials = new unsigned long int[n+1];
    factorials[0] = 1;
    for(int i = 1; i<=n; ++i)
        factorials[i] = factorials[i-1] * i;

    char *tab = new char[n];

    // Initialization with the first combination 0123...n-1
    for(int i(0); i<n; ++i)
    {
        tab[i] = i;
        cout << str[i] << " ";
    }
    cout << endl;

    for(unsigned long int i(1); i < factorials[n]; ++i)
    {
        for (int j(0); j < n; ++j)
        {
            if(i % factorials[n-j-1] == 0)
            {
                // increment tab[j] (or find the next available)
                SetNextAvailable(tab, j, n);
            }
        }
        for (int j(0); j < n; ++j)
        {
            cout << str[tab[j]] << " "; 
        }
        cout << endl;
    }

    delete [] factorials;
}

Функция SetNextAvailable()

void SetNextAvailable(char *tab, int j, int n)
{
    bool finished;
    do
    {
        finished = true;
        ++(*(tab+j));
        if (*(tab+j) == n) *(tab+j) = 0;
        for (int i(0); i < j; ++i)
        {
            if ( *(tab+i) == *(tab+j) )
            {
                finished = false;
                break;
            }
        }
    } while(finished == false);
}

Функция AddOne()

bool AddOne(int *tab, int k, int n)
{
    int i;
    for(i=k; i>=0; --i)
    {
        if(((++tab[i]) + (k-i)) != n)
            break;
    }
    if(i == -1)
        return false;
    else
    {
        for(int j=i+1; j<=k; ++j)
        {
            tab[j] = tab[j-1] + 1;
        }
        return true;
    }
}