7

假设我有一个包含单个字符的任意大小的数组。我想计算这些字符的所有可能组合，直到任意长度。

所以假设我的数组是 [1, 2, 3]。用户指定的长度为 2。那么可能的组合为 [11, 22, 33, 12, 13, 23, 21, 31, 32]。

我很难找到一个允许任意长度而不仅仅是排列数组的合适算法。哦，虽然速度不是绝对关键，但它也应该相当快。

4

7 回答 7

9

只需使用进位进行添加即可。

假设您的数组包含 4 个符号，并且您想要长度为 3 的符号。

以 000 开头（即单词上的每个符号 = 字母 [0]）

然后加起来：

000 001 002 003 010 011 ...

该算法（给定这些索引）只是增加最低数字。如果它达到字母表中的符号数量，则增加前一个数字（遵循相同的规则）并将当前设置为 0。

C++ 代码：

int N_LETTERS = 4;
char alphabet[] = {'a', 'b', 'c', 'd'};

std::vector<std::string> get_all_words(int length)
{
  std::vector<int> index(length, 0);
  std::vector<std::string> words;

  while(true)
  {
    std::string word(length);
    for (int i = 0; i < length; ++i)
      word[i] = alphabet[index[i]];
    words.push_back(word);

    for (int i = length-1; ; --i)
    { 
      if (i < 0) return words;
      index[i]++;
      if (index[i] == N_LETTERS)
        index[i] = 0;
      else
        break;
    }
  }
}

代码未经测试，但应该可以解决问题。

于 2010-03-04T16:46:13.457 回答
2

一种方法是使用一个简单的计数器，您在内部将其解释为基数 N，其中 N 是数组中的项目数。然后，您从基数 N 计数器中提取每个数字，并将其用作数组的索引。所以如果你的数组是 [1,2] 并且用户指定的长度是 2，你有

Counter = 0, indexes are 0, 0
Counter = 1, indexes are 0, 1
Counter = 2, indexes are 1, 0
Counter = 3, indexes are 1, 1

这里的诀窍是你的 base-10 到 base-N 的转换代码，这并不难。

于 2010-03-04T16:47:33.093 回答
2

Knuth 在The Art of Computer Programming , vol 1中深入介绍了组合和排列。这是我几年前写的他的一种算法的实现（不要讨厌这种风格，它的古老代码）：

#include <algorithm>
#include <vector>
#include <functional>
#include <iostream>
using namespace std;

template<class BidirectionalIterator, class Function, class Size>
Function _permute(BidirectionalIterator first, BidirectionalIterator last, Size k, Function f, Size n, Size level)
{
    // This algorithm is adapted from Donald Knuth, 
    //      "The Art of Computer Programming, vol. 1, p. 45, Method 1"
    // Thanks, Donald.
    for( Size x = 0; x < (n-level); ++x )   // rotate every possible value in to this level's slot
    {
        if( (level+1) < k ) 
            // if not at max level, recurse down to twirl higher levels first
            f = _permute(first,last,k,f,n,level+1);
        else
        {
            // we are at highest level, this is a unique permutation
            BidirectionalIterator permEnd = first;
            advance(permEnd, k);
            f(first,permEnd);
        }
        // rotate next element in to this level's position & continue
        BidirectionalIterator rotbegin(first);
        advance(rotbegin,level);
        BidirectionalIterator rotmid(rotbegin);
        rotmid++;
        rotate(rotbegin,rotmid,last);
    }
    return f;
}

template<class BidirectionalIterator, class Function, class Size>
Function for_each_permutation(BidirectionalIterator first, BidirectionalIterator last, Size k, Function fn)
{
    return _permute<BidirectionalIterator,Function,Size>(first, last, k, fn, distance(first,last), 0);
}   





template<class Elem>
struct DumpPermutation : public std::binary_function<bool, Elem* , Elem*>
{
    bool operator()(Elem* begin, Elem* end) const
    {
        cout << "[";
        copy(begin, end, ostream_iterator<Elem>(cout, " "));
        cout << "]" << endl;
        return true;
    }
};

int main()
{

    int ary[] = {1, 2, 3};
    const size_t arySize = sizeof(ary)/sizeof(ary[0]);

    for_each_permutation(&ary[0], &ary[arySize], 2, DumpPermutation<int>());

    return 0;
}

该程序的输出是：

[1 2 ]
[1 3 ]
[2 3 ]
[2 1 ]
[3 1 ]
[3 2 ]

如果您希望您的组合包含重复元素，如 [11] [22] 和 [33]，您可以使用上面的算法生成组合列表，然后通过执行以下操作将新元素附加到生成的列表中：

for( size_t i = 0; i < arySize; ++i )
{
    cout << "[";
    for( int j = 0; j < k; ++j )
        cout << ary[i] << " ";
    cout << "]" << endl;
}

...现在程序输出变为：

[1 2 ]
[1 3 ]
[2 3 ]
[2 1 ]
[3 1 ]
[3 2 ]
[1 1 ]
[2 2 ]
[3 3 ]
于 2010-03-04T17:26:50.270 回答
1

如果您事先知道长度，那么您只需要一些 for 循环。说，对于长度= 3：

for ( i = 0; i < N; i++ )
   for ( j = 0; j < N; j++ )
      for ( k = 0; k < N; k++ )
         you now have ( i, j, k ), or a_i, a_j, a_k

现在概括它，只需递归地执行，递归的每一步都使用 for 循环之一：

recurse( int[] a, int[] result, int index)
    if ( index == N ) base case, process result
    else
        for ( i = 0; i < N; i++ ) {
           result[index] = a[i]
           recurse( a, result, index + 1 )
        }

当然，如果您只是想要所有组合，您可以将每个步骤视为一个N基于 - 的数字，从1到k^N - 1，其中k是长度。

基本上你会得到，在基数N（k= 4）：

0000 // take the first element four times
0001 // take the first element three times, then the second element
0002 
...
000(N-1) // take the first element three times, then take the N-th element
1000 // take the second element, then the first element three times
1001 
..
(N-1)(N-1)(N-1)(N-1) // take the last element four times
于 2010-03-04T16:47:42.280 回答
0

使用彼得的算法效果很好；但是，如果您的字母集太大或字符串太长，则尝试将所有排列放入一个数组并返回该数组是行不通的。数组的大小将是字母表的大小，提升到字符串的长度。

我在 perl 中创建了这个来解决这个问题：

package Combiner;
#package used to grab all possible combinations of a set of letters. Gets one every call, allowing reduced memory usage and faster processing.
use strict;
use warnings;

#initiate to use nextWord
#arguments are an array reference for the list of letters and the number of characters to be in the generated strings.
sub new {
    my ($class, $phoneList,$length) = @_;
    my $self = bless {
        phoneList => $phoneList,
        length => $length,
        N_LETTERS => scalar @$phoneList,
    }, $class;
    $self->init;
    $self;
}

sub init {
    my ($self) = shift;
    $self->{lindex} = [(0) x $self->{length}];
    $self->{end} = 0;
    $self;
}

#returns all possible combinations of N phonemes, one at a time. 
sub nextWord {
    my $self = shift;
    return 0 if $self->{end} == 1;
    my $word = [('-') x $self->{length}];

    $$word[$_] = ${$self->{phoneList}}[${$self->{lindex}}[$_]]
        for(0..$self->{length}-1);

    #treat the string like addition; loop through 000, 001, 002, 010, 020, etc.
    for(my $i = $self->{length}-1;;$i--){
         if($i < 0){
            $self->{end} = 1;
            return $word;
         }
         ${$self->{lindex}}[$i]++;
         if (${$self->{lindex}}[$i] == $self->{N_LETTERS}){
            ${$self->{lindex}}[$i] = 0;
         }
         else{
            return $word;
         }
    }
}

像这样称呼它：my $c = Combiner->new(['a','b','c','d'],20);。然后打电话nextWord抢下一个字；如果nextWord返回 0，则表示已完成。

于 2011-07-19T17:20:12.747 回答
0

这是我在 Haskell 中的实现：

g :: [a] -> [[a]] -> [[a]]
g alphabet = concat . map (\xs -> [ xs ++ [s] | s <- alphabet])

allwords :: [a] -> [[a]]
allwords alphabet = concat $ iterate (g alphabet) [[]]

将此脚本加载到GHCi中。假设我们想在字母表 {'a','b','c'} 上找到所有长度小于或等于 2 的字符串。以下GHCi会话执行此操作：

*Main> take 13 $ allwords ['a','b','c']
["","a","b","c","aa","ab","ac","ba","bb","bc","ca","cb","cc"]

或者，如果您只想要长度等于 2 的字符串：

*Main> filter (\xs -> length xs == 2) $ take 13 $ allwords ['a','b','c']
["aa","ab","ac","ba","bb","bc","ca","cb","cc"]

小心，allwords ['a','b','c']因为它是一个无限的列表！

于 2012-10-02T08:03:35.620 回答
0

这是我写的。可能对你有帮助...

#include<stdio.h>
#include <unistd.h>
void main()
{
FILE *file;
int i=0,f,l1,l2,l3=0;
char set[]="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ01234567890!@#$%&*.!@#$%^&*()";
int size=sizeof(set)-1;
char per[]="000";
//check urs all entered details here//
printf("Setlength=%d Comination are genrating\n",size);

// writing permutation here for length of 3//
for(l1=0;l1<size;l1++)
//first for loop which control left most char printed in file//
{ 
per[0]=set[l1];
// second for loop which control all intermediate char printed in file//
for(l2=0;l2<size;l2++)
{
per[1]=set[l2];
//third for loop which control right most char printed in file//
for(l3=0;l3<size;l3++)
{
per[2]=set[l3];
//apend file (add text to a file or create a file if it does not exist.//
file = fopen("file.txt","a+");
//writes array per to file named file.txt// 
fprintf(file,"%s\n",per); 
///Writing to file is completed//
fclose(file); 
i++;
printf("Genrating Combination  %d\r",i);
fflush(stdout);``
usleep(1);
}
}
}
printf("\n%d combination has been genrate out of entered data of length %d \n",i,size);
puts("No combination is left :) ");
puts("Press any butoon to exit");
getchar();
}
于 2013-03-17T18:50:51.257 回答