Скажите, что у меня есть массив произвольного размера, содержащего отдельные символы. Я хочу вычислить все возможные комбинации тех символов до произвольной длины.
Так позволяет, говорят, что мой массив [1, 2, 3]. Указанная пользователями длина равняется 2. Затем возможные комбинации [11, 22, 33, 12, 13, 23, 21, 31, 32].
Я испытываю реальные затруднения при нахождении подходящего алгоритма, который позволяет произвольные длины и не только переставляет массив. О, и в то время как скорость не является абсолютно критической, это должно быть довольно быстро также.
Просто добавьте с переносом.
Допустим, ваш массив содержит 4 символа, и вам нужны символы длины 3.
Начните с 000 (т.е. каждый символ в вашем слове = алфавит [0])
Затем сложите:
000 {{1 }} 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;
}
}
}
Код не тестировался, но должен помочь.
Если вы заранее знаете длину, все, что вам нужно, - это петли для петель. Скажем, for length = 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
Один из способов сделать это - использовать простой счетчик, который вы внутренне интерпретируете как основание 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, что не так уж сложно.
Кнут подробно описывает комбинации и перестановки в Искусство компьютерного программирования , том 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 ]