単一の文字を保持する任意のサイズの配列があるとします。任意の長さまで、これらの文字の可能なすべての組み合わせを計算したいと思います。
したがって、私の配列が [1, 2, 3] であるとしましょう。ユーザー指定の長さは 2 です。可能な組み合わせは [11, 22, 33, 12, 13, 23, 21, 31, 32] です。
配列を並べ替えるだけでなく、任意の長さを許可する適切なアルゴリズムを見つけるのに本当に苦労しています。ああ、速度は絶対に重要というわけではありませんが、適度に高速であるべきです。
キャリーで加算するだけです。
配列に 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;
}
}
}
コードはテストされていませんが、うまくいくはずです。
これを行う 1 つの方法は、基数 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 への変換コードです。これはそれほど難しくありません。
Knuth は、The Art of Computer Programming vol 1 で組み合わせと順列についてある程度詳しく説明しています。これは、私が数年前に書いた彼のアルゴリズムの 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 ]
事前に長さがわかっている場合、必要なのは 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 ループの 1 つを使用して、再帰的に実行します。
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基づく数値と考えることができます。ここで、 は長さです。1k^N - 1k
基本的に、ベースで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
Peter のアルゴリズムを使用するとうまくいきます。ただし、文字セットが大きすぎるか、文字列のサイズが長すぎる場合、すべての順列を配列に入れて配列を返そうとしてもうまくいきません。配列のサイズは、アルファベットを文字列の長さに合わせたサイズになります。
問題を処理するために、これを 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次に、次の単語を取得するために呼び出します。nextWord0 を返す場合は、完了したことを意味します。
これは私が書いたものです。あなたに役立つかもしれません...
#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();
}