Recursive permutations with repetition

Question

I'm trying to write a recursive function that gets all permutations with repetitions of a given list.

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

I want a recursive version of this code so I can get permutations for sets of any size:

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

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

      }
   }
}

I'm having some trouble wrapping my head around the problem. So far I'm thinking I need to find when I've reached an arbitrary depth to stop re-cursing.

Edit: I'd prefer a pseudo-code solution, I'm not implementing this in C++

Answer 1

Given that you want both AAB and ABA to be output, you are looking for permutations rather than combinations. In particular, you are looking for the unique permutations of a set of size k where the elements are drawn with replacement from a set of n tokens. The number of combinations is _n+k-1C_k while the number of permutations is n^k.

Pseudo-code that illustrates these two concepts:

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

A working C++ implementation:

#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

I think an iterative solution will be more efficient, and it can be written to support arbitrary dimensions and numbers of symbols. The code is in C++, but I delibaretely kept it simple so that you can easily translate into pseudocode or other language:

#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
    }
}

The output should be:

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 ADC BDC CDC DDC AAD BAD CAD DAD ABD BBD CBD DBD ACD BCD CCD DCD ADD BDD CDD DDD

If you want the symbols in the last position to change fastest, just reverse the contents of each row of the generated output.

Of course, you can make generate_combinations a template function and make it work with other types than char.

============ UPDATE =================

A recursive solution is, of course, more elegant:

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

Use it in place of generate_combinations function in the first program. It should give you the same output as before.

Answer 3

Here is my Java solution:

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

I included the iterative one because I hadn't realised you needed a recursive solution at the start. Let me explain it from a pseudo code perspective:

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

The function returns a list of all the combinations that are possible. I thought of the problem by defining the result set first in my head. The result set consists of an array of strings which all have the same length as the original string and for every substring, the preceding character can be any character from the original string. That's it.

So we'll just assume we have a function which generates each substring and work on the rest of it.

Array somearray;

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

To then generate substrings, it is the exact same problem but with length of one less than the current string. This is the exact same function (and that's how it's recursive). We only need the base case, of when the length is 0 in which case we return an empty string which is appended to each character.

Sorry if you don't understand my explanation, wasn't really sure how to best do it. Java is fairly close to pseudo-code so it shouldn't be too hard to figure out.

Answer 4

//Unique Combinations using recursion

//Here I modified the idea of using prefix to carry over in recursion to just carrying //over the index so that objects can be the arguments rather than just strings.

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

}

Answer 5

@Jan Even tho' it seems your downvote for my preceeding answer was somewhat arbitrary, I accepted your challenge and came up with this answer which satisfies your own desire for making calls for combinations of any size taken from the entire set.

Recursively, a very simple answer, combo, in Free Pascal. n is the size of the entire set, k is the subset size requested.

    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 disposes of the productarray[] made for each combination.

Answer 6

Building on a very simple and elegant recursive solution provided by Adam under a different question: 'Algorithm to return all combinations of k elements from n', which you can find elsewhere.

Adam's answer provides, however, for obtaining all combinations from a given set, which doesn't exactly fit the question under which his answer was given, but I found his answer suited the purpose of my research perfectly. I look for value wherever I might find it. And it does fit this present question.

I developed the following program using Open Arrays in Free Pascal to produce all combinations of items in any given array. The open array allows for an arbitrary and dynamically variable number of items, and each item can be any kind of variable or record. This program has items of long integers, but could also be used for pointers to other variables. I used it that way to determine the most efficient way of cutting metal bars into various lengths of shorter bars, by examining the various possible combinations of shorter bars of different lengths which fit into the raw material bars.

The procedure combo recurses once for every possible combination, but the depth of recursion is only one level deeper than the number of items in the 'pending' source array. Passing the parameters to the combo procedure by reference is not necessary, but doing so cuts the operational memory requirement nearly in half.

    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
    *