logo标签列表

重复排列的递归排列

algorithmmathrecursion
4
我正在尝试编写一个递归函数，用于获取给定列表的所有重复排列。
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++ {

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

      }
   }
}

我对这个问题感到有些困扰。到目前为止，我认为我需要找到何时达到任意深度以停止递归。

编辑：我更喜欢一种伪代码的解决方案，我不会用C++实现它。

标记一个适当的语言会吸引更多关注该问题。 - Mahesh
这种语言没有标签。我正在使用“breve”编程环境。 - infM
2
有点挑剔，AAB 和 ABA 是相同的组合。我认为你的意思是排列(permutations)，而不是组合(combinations)。 - David Hammen
6个回答
4
考虑到你想要输出AAB和ABA，你需要寻找排列而不是组合。特别地，你需要从一组大小为k的元素中有放回地选择，并找出其独特的排列。组合数为n+k-1Ck，而排列数为nk。
以下是说明这两个概念的伪代码：
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;
}
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 ADC BDC CDC DDC AAD BAD CAD DAD ABD BBD CBD DBD ACD BCD CCD DCD ADD 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函数。它应该会给你和之前相同的输出结果。

谢谢，我会看一下的。不过，我想继续走递归的路线，直到我把它弄好为止 :) - infM
好的，给你一个递归解决方案。 - quant_dev
1

这是我的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与伪代码非常接近，因此应该不难弄清楚。
递归代码存储了组合列表的2个副本（subs和arr），这可以避免。 - quant_dev
是的。我为了可读性将其删除了。不存储生成的首字母是微不足道的。 - Mike Kwan
顺便问一句，“Java相当接近伪代码”是故意用反语表达的吗？ - quant_dev
嗯，不是C++，更接近于伪代码而已 ;) - Mike Kwan
0

@Jan 即使你对我之前的回答进行了无端的负评，我接受了你的挑战，并提供了这个答案，满足了你自己对从整个集合中取任意大小的组合进行调用的需求。

递归地，一个非常简单的答案，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;

生产者 处理每个组合制作的 productarray[]。

发布了这个之后，我注意到它的逻辑与Hajmola给出的非常相似。 - Lor
0

//使用递归实现唯一组合

//我这里修改了使用前缀在递归中进行传递的思路，只需传递索引即可，因此可以将对象作为参数而不仅仅是字符串。

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

}

-1

在Adam提供的一个不同问题下提供了一个非常简单而优雅的递归解决方案的基础上：'从n个元素中返回所有k个元素的组合算法'，你可以在其他地方找到。

然而，Adam的答案提供了从给定集合获取所有组合的方法，这并不完全符合他所回答的问题，但我发现他的答案完美地适合我的研究目的。我会在任何地方寻找价值。它确实适用于这个问题。

我使用Free Pascal中的Open Arrays开发了以下程序，以生成任何给定数组中项目的所有组合。开放数组允许任意和动态可变数量的项目，并且每个项目可以是任何类型的变量或记录。该程序具有长整数项，但也可以用于指向其他变量的指针。我将其用于通过检查不同长度的短条的各种可能组合来确定将金属棒切割成各种长度的短条的最有效方法。

过程combo对于每个可能的组合仅递归一次，但递归深度仅比“待处理”源数组中的项目数多一级。将参数通过引用传递给combo过程并不是必要的，但这样做可以将操作内存需求减少近一半。

    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
    *
OP希望对任意大小的集合进行组合，而不是一次性列出所有可能的大小。 - Jan Doggen
引用OP的话：“我正在尝试编写一个递归函数，以获取给定列表的所有组合。” - Lor
@jan - 可以很容易地更改上面的“produce”过程，以仅传递包含所需数量项目的数组。这不是限制输出的最有效方法，但它可以工作。 - Lor
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接