Рекурсивные комбинации

Question

Я пытаюсь написать рекурсивную функцию, которая получает все комбинации данного списка.

Eg. set = ABC
1. AAA
2. AAB
3. AAC
4. ABA 
N. CCC

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

for i=0; i<S.size(); i++ {
   for j=0; j<S.size(); j++ {
      for k=0; k<S.size(); k++ {

         combo[0] = S[i];
         combo[1] = S[j];
         combo[2] = S[k];
         combinations.push(combo);

      }
   }
}

У меня возникли проблемы с тем, чтобы обернуть голову вокруг этой проблемы. До сих пор я думаю, что мне нужно найти, когда я достигну произвольной глубины, чтобы перестать ругаться.

Edit: я бы предпочел решение с псевдокодом, я не реализую это в C ++

Answer 1

Учитывая, что вы хотите, чтобы выводились и AAB, и ABA, вы ищете перестановок , а не комбинаций . В частности, вы ищете уникальные перестановки из набора размером k , где элементы рисуются с заменой из набора n токенов. Количество комбинаций равно _{n + k-1} C _k , а число перестановок равно n ^k .

Псевдокод, иллюстрирующий эти два понятия:

build_combinations (tokens, set_size)
  Arrangements combos
  if (set_size == 0)
    combos.add ("")
  else
    Comment: tail_substrings of "ABC" is ("ABC", "BC", "C").
    foreach tail (tail_substrings (tokens))
      foreach sub_combo (build_combinations (tail, set_size-1))
        combos.add (tail.first() + sub_combo)
  return combos

build_permutations (tokens, set_size)
  Arrangements perms
  if (set_size == 0)
    perms.add ("")
  else
    sub_perms = build_permutations (tokens, set_size-1)
    foreach token (tokens)
      foreach perm (sub_perms)
        perms.add (cur_token + *rem_iter)
  return perms

Работающая реализация C ++:

#include <string>
#include <vector>

typedef std::string::const_iterator StringIterator;
typedef std::vector<std::string> Arrangements;
typedef Arrangements::const_iterator ArrangementsIterator;

Arrangements build_combinations (const std::string & tokens, unsigned set_size)
{
  Arrangements combos;
  if (set_size == 0) {
    combos.push_back ("");
  }   
  else {
    for (StringIterator token_iter = tokens.begin();
         token_iter != tokens.end();
         ++token_iter) {
      std::string cur_token(1, *token_iter);
      std::string rem_tokens(token_iter, tokens.end());
      Arrangements rem_combos = build_combinations (rem_tokens, set_size-1);
      for (ArrangementsIterator rem_iter = rem_combos.begin();
           rem_iter != rem_combos.end();
           ++rem_iter) {
         combos.push_back (cur_token + *rem_iter);
      }
    }
  }   
  return combos;
}   

Arrangements build_permutations (const std::string & tokens, unsigned set_size)
{
  Arrangements perms;
  if (set_size == 0) {
    perms.push_back ("");
  }
  else {
    Arrangements rem_perms = build_permutations (tokens, set_size-1);
    for (StringIterator token_iter = tokens.begin();
         token_iter != tokens.end();
         ++token_iter) {
      std::string cur_token(1, *token_iter);
      for (ArrangementsIterator rem_iter = rem_perms.begin();
           rem_iter != rem_perms.end();
           ++rem_iter) {
         perms.push_back (cur_token + *rem_iter);
      }
    }
  }
  return perms;
}

Answer 2

Я думаю, что итеративное решение будет более эффективным, и оно может быть написано для поддержки произвольных измерений и количества символов. Код написан на C ++, но я намеренно упростила его, чтобы вы могли легко перевести его на псевдокод или другой язык:

#include <vector>
#include <cassert>
#include <iostream>

void generate_combinations(const std::vector<char>& symbols, const unsigned int dimension, std::vector<std::vector<char> >& output)
{
    assert( symbols.size() ); // terminate the program if condition not met
    std::vector<char> current_output(dimension);
    std::vector<unsigned int> current_combo(dimension + 1, 0);
    const unsigned int max_symbol_idx = symbols.size() - 1;
    size_t current_index = 0;
    while (current_combo.back() == 0) {
        // add current combination
        for (unsigned int i = 0; i < dimension; ++i) {
            current_output[i] = symbols[current_combo[i]];
        }
        output.push_back(current_output);

        // move to next combination
        while (current_index <= dimension && current_combo[current_index] == max_symbol_idx) {
            current_combo[current_index] = 0;
            ++current_index;
        }
        if (current_index <= dimension) {
            ++current_combo[current_index];
        }
        current_index = 0;
    }
}

int main()
{
    const unsigned int dimension = 3;
    std::vector<char> symbols(4);   
    symbols[0] = 'A';
    symbols[1] = 'B';
    symbols[2] = 'C';
    symbols[3] = 'D';
    std::vector<std::vector<char> > output;
    generate_combinations(symbols, dimension, output);
    for (unsigned int i = 0; i < output.size(); ++i) {
        for (unsigned int j = 0; j < dimension; ++j) {
            std::cout << output[i][j]; // write symbol to standard output
        }
        std::cout << std::endl; // write new line character
    }
}

Вывод должен быть:

AAA BAA CAA DAA ABA BBA CBA DBA ACA BCA CCA DCA ADA BDA CDA DDA AAB BAB CAB DAB ABB BBB CBB DBB ACB BCB CCB DCB ADB BDB CDB DDB AAC BAC CAC DAC ABC BBC CBC DBC ACC BCC CCC DCC АЦП BDC CDC DDC AAD BAD CAD DAD ABD BBD CBD DBD ACD BCD CCD DCD ДОБАВИТЬ BDD CDD DDD

Если вы хотите, чтобы символы в последней позиции менялись быстрее, просто измените содержимое каждой строки сгенерированного вывода.

Конечно, вы можете сделать generate_combinations функцией шаблона и заставить ее работать с другими типами, кроме char.

============ ОБНОВЛЕНИЕ =================

Рекурсивное решение, конечно, более элегантно:

void add_next_symbol(const std::vector<char>& symbols, const unsigned int dimension, std::vector<char>& current_output, std::vector<std::vector<char> >& output)
{
    if (dimension == 0) {
        output.push_back(current_output);
    } else {
        for (unsigned int i = 0; i < symbols.size(); ++i) {
            current_output.push_back(symbols[i]);
            add_next_symbol(symbols, dimension - 1, current_output, output);
            current_output.pop_back();
        }
    }
}

void generate_combinations_recursive(const std::vector<char>& symbols, const unsigned int dimension, std::vector<std::vector<char> >& output)
{
    std::vector<char> current_output;
    add_next_symbol(symbols, dimension, current_output, output);
}

Используйте его вместо функции generate_combinations в первой программе. Он должен дать вам тот же вывод, что и раньше.

Answer 3

Вот мое решение на Java:

public class Combination {
  public List<String> recurse( String orig, int len ) {
    if( len == 0 ) {
      List<String> arr = new ArrayList<String>();
      arr.add("");
      return arr;
    } else {
      List<String> arr  = new ArrayList<String>();
      List<String> subs = recurse(orig, len - 1);

      for( int i = 0; i < orig.length(); i++ ) {
        String cur = Character.toString(orig.charAt(i));

        for( String sub : subs ) {
          arr.add(cur + sub);
        }
      }

      return arr;
    }
  }

  public static void main(String[] args) {
    String set = "ABC";

    Combination c = new Combination();
    for( String s : c.recurse(set, set.length()) ) {
      System.out.println(s);
    }
//    for( int i = 0; i < set.length(); i++ ) {
//      for( int j = 0; j < set.length(); j++ ) {
//        for( int k = 0; k < set.length(); k++ ) {
//          StringBuilder s = new StringBuilder();
//          s.append(set.charAt(i));
//          s.append(set.charAt(j));
//          s.append(set.charAt(k));
//          
//          System.out.println(s.toString());
//        }
//      }
//    }
  }
}

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

public List<String> recurse( String orig, int len ) {
  if( len == 0 ) {
    List<String> arr = new ArrayList<String>();
    arr.add("");
    return arr;
  } else {
    List<String> arr  = new ArrayList<String>();
    List<String> subs = recurse(orig, len - 1);

    for( int i = 0; i < orig.length(); i++ ) {
      String cur = Character.toString(orig.charAt(i));

      for( String sub : subs ) {
        arr.add(cur + sub);
      }
    }

    return arr;
  }
}

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

Итак, мы просто предположим, что у нас есть функция, которая генерирует каждую подстроку и работает с остальной ее частью.

Array somearray;

for( int i = 0; i < orig.length(); i++ ) {
  for( String s : getSubstrings() ) {
    Array.add( originalString.charAt(i) + s );
  }
}

Чтобы затем генерировать подстроки, она точно такая жепроблема, но с длиной на одну строку меньше текущейЭто точно такая же функция (и вот как она рекурсивна).Нам нужен только базовый случай, когда длина равна 0, и в этом случае мы возвращаем пустую строку, которая добавляется к каждому символу.

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

Answer 4

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

Рекурсивно, очень простой ответ, combo, в Free Pascal. n - это размер всего набора, k - запрашиваемый размер подмножества.

    procedure combinata (n, k :integer; producer :oneintproc);

        procedure combo (ndx, nbr, len, lnd :integer);
        begin
            for nbr := nbr to len do begin
                productarray[ndx] := nbr;
                if len < lnd then
                    combo(ndx+1,nbr+1,len+1,lnd)
                else
                    producer(k);
            end;
        end;

    begin
        combo (0, 0, n-k, n-1);
    end;

producer располагает productarray[], сделанным для каждой комбинации.

Answer 5

Основываясь на очень простом и элегантном рекурсивном решении, предложенном Адамом по другому вопросу: «Алгоритм возврата всех комбинаций k элементов из n», который вы можете найти в другом месте.

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

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

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

    program combinata;

    uses
        SYSUTILS;

    type
        combarry = array of longint;

    var
        testc, testp :combarry;

        procedure produce (var cmb :combarry);
        var  x :integer;
        begin
            for x := 0 to length(cmb)-1 do begin
                if x > 0 then write(',');
                write(cmb[x]:0);
            end;
            writeln;
        end;

    procedure combo (var current, pending :combarry);
    var
        x, len  :integer;
        newcurrent, newpending  :combarry;

    begin
        if length(pending) = 0 then
            if length(current) > 0 then produce(current) else
        else begin

            {append 1st element of pending as the last element on current}
            newcurrent := current;
            len := length(newcurrent);
            setlength(newcurrent,len+1);
            newcurrent[len] := pending[0];

            {remove the first element from pending}
            len := length(pending) - 1;
            setlength(newpending,len);
            for x := len downto 1 do newpending[x-1] := pending[x];

            combo(newcurrent,newpending);
            combo(current,newpending);
        end;
    end;

    begin
        setlength(testc,0);
        setlength(testp,4);
        testp[0] := 5;
        testp[1] := 10;
        testp[2] := 15;
        testp[3] := 20;
        combo(testc, testp);
        writeln('*');
    end.

    Running this produces:
    5,10,15,20
    5,10,15
    5,10,20
    5,10
    5,15,20
    5,15
    5,20
    5
    10,15,20
    10,15
    10,20
    10
    15,20
    15
    20
    *

Answer 6

// Уникальные комбинации с использованием рекурсии

// Здесь я изменил идею использования префикса для переноса в рекурсии, чтобы просто переносить // индекс, чтобы объекты могли быть аргументами, а не просто строками.

public static void main(String[] args) {


    int k = 20;

    Object[] nums = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    Object[] chars = { 'a', 'b', 'c', 'd', 'e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
    Object[] aux = new Object[k];



    long start = System.currentTimeMillis();
    combination(chars, 0, 0, k, aux);
    //combination(nums, 0, 0, k, aux);

    System.out.println("Time: "+ (System.currentTimeMillis()-start));
}

public static void combination(Object[] s, int index, int next, int k,
        Object[] aux) {

    //this is the base case
    //if the index has reached k then print out the aux which holds the combination
    if (index == k) {
        show(aux);          
    }else{//here you spawn loops

        for (int i = next; i < s.length; i++) {

            aux[index] = s[i];
            combination(s, index + 1, i + 1, k, aux);
        }
    }
}

private static void show(Object[] x) {
    for (int i = 0; i < x.length; i++)
        System.out.print(x[i] + " ");
    System.out.println();
}

}