Como chegar contagem dos próximos combinações para determinado conjunto?
-
13-09-2019 - |
Pergunta
- Eu editei o texto original para salvar potenciais leitores algum tempo e saúde. Talvez alguém vai realmente usar isso.
Eu sei que é material básico. Provavelmente como muito, muito básico.
Como obter todas as combinações possíveis de determinado conjunto.
por exemplo
set string = "abc";
I espera obter:
a b c aa ac ab aaa AAB AAC aba abb abc aca acb acc baa bab ...
ea lista continua (se há limite para o comprimento é definido).
Eu estou procurando um código muito limpo para isso - tudo o que eu encontrei foi uma espécie de sujo e não funcionando corretamente. O mesmo posso dizer sobre o código que eu escrevi.
Eu preciso tal código, porque eu estou escrevendo força bruta (md5) implementação de trabalho em vários segmentos. O padrão é que não há processo Pai que alimenta segmentos com pedaços de suas próprias combinações, para que pudessem trabalhar sobre estes por conta própria.
Exemplo: primeiro segmento recebe pacote de 100 permutações, segundo fica próximo 100 etc.
Deixe-me saber se eu deveria publicar o lugar final do programa.
EDIT # 2
Mais uma vez agradecer a vocês.
Graças a você que eu terminei o meu pedido Escravo / Mestre Brute-Force implementado com MPICH2 (sim, pode trabalhar sob Linux e Windows através por exemplo de rede) e, desde o dia está quase aqui, e eu já perdi um monte de tempo (e sol) Eu vou continuar com a minha próxima tarefa ... :)
Você me mostrou que comunidade StackOverflow é incrível - graças
Solução
Aqui está algum código C ++ que gera permutações de um poder configurado para um determinado comprimento.
A função getPowPerms
leva um conjunto de caracteres (tal como um vector de cordas) e um comprimento máximo, e retorna um vector de cordas permutadas:
#include <iostream>
using std::cout;
#include <string>
using std::string;
#include <vector>
using std::vector;
vector<string> getPowPerms( const vector<string>& set, unsigned length ) {
if( length == 0 ) return vector<string>();
if( length == 1 ) return set;
vector<string> substrs = getPowPerms(set,length-1);
vector<string> result = substrs;
for( unsigned i = 0; i < substrs.size(); ++i ) {
for( unsigned j = 0; j < set.size(); ++j ) {
result.push_back( set[j] + substrs[i] );
}
}
return result;
}
int main() {
const int MAX_SIZE = 3;
string str = "abc";
vector<string> set; // use vector for ease-of-access
for( unsigned i = 0; i < str.size(); ++i ) set.push_back( str.substr(i,1) );
vector<string> perms = getPowPerms( set, MAX_SIZE );
for( unsigned i = 0; i < perms.size(); ++i ) cout << perms[i] << '\n';
}
Quando executado, este exemplo impressões
a b c aa ba ca ab bb cb ... acc bcc ccc
Update: Não tenho certeza se isso é útil, mas aqui é um "gerador" função chamada next
que cria o próximo item na lista dada o item atual.
Talvez você poderia gerar os primeiros N itens e enviá-los em algum lugar, em seguida, gerar os próximos N itens e enviá-los em outro lugar.
string next( const string& cur, const string& set ) {
string result = cur;
bool carry = true;
int loc = cur.size() - 1;
char last = *set.rbegin(), first = *set.begin();
while( loc >= 0 && carry ) {
if( result[loc] != last ) { // increment
int found = set.find(result[loc]);
if( found != string::npos && found < set.size()-1 ) {
result[loc] = set.at(found+1);
}
carry = false;
} else { // reset and carry
result[loc] = first;
}
--loc;
}
if( carry ) { // overflow
result.insert( result.begin(), first );
}
return result;
}
int main() {
string set = "abc";
string cur = "a";
for( int i = 0; i < 20; ++i ) {
cout << cur << '\n'; // displays a b c aa ab ac ba bb bc ...
cur = next( cur, set );
}
}
Outras dicas
C ++ tem uma função next_permutation (), mas eu não acho que isso é o que você quer.
Você deve ser capaz de fazê-lo facilmente com uma função recursiva. por exemplo.
void combinations(string s, int len, string prefix) {
if (len<1) {
cout << prefix << endl;
} else {
for (int i=0;i<s.size();i++) {
combinations(s, len-1, prefix + s[i])
}
}
}
EDIT: Para a parte threading, eu suponho que você está trabalhando em um forcer senha bruta ??p>?
Se assim for, eu adivinhar a senha testando parte é o que você quiser acelerar ao invés de geração de senha.
Portanto, você poderia simplesmente criar um processo pai que gera todas as combinações, então cada k th senha é dada para enfiar k mod N (onde N é o número de threads) para verificação.
Outra versão da permutação está na biblioteca padrão do Python, embora você questionada em C ++.
http://docs.python.org/library/itertools.html # itertools.permutations
Mas a sua lista contém uma seqüência de infinitivo de um cada personagem, então eu acho que o método que como requisitar aqueles devem ser definidos primeiro, e indicar o seu algoritmo de forma clara.
Eu não posso dar-lhe o código, mas o que você precisa é de um algoritmo recursivo aqui é algum código pseudo
A idéia é simples, concatenar cada corda em seu conjunto com cada outra corda, em seguida, permutar as cordas. adicionar todos os seus strings menores para o seu conjunto e fazer a mesma coisa outra vez com o novo conjunto. Continue indo até você está cansado:)
Pode ser um pouco confuso, mas pensar um pouco;)
set = { "a", "b", "c"}
build_combinations(set)
{
new_set={}
for( Element in set ){
new_set.add(Element);
for( other_element in set )
new_element = concatinate(Element, other_element);
new_set.add(new_element);
}
new_set = permute_all_elements(new_set);
return build_combinations(new_set);
}
Isto, obviamente, causa um estouro de pilha, porque não há nenhuma condição de terminação :) para colocar nas build_combinations funcionar o que sempre condicionar você gosta (talvez tamanho do set?) Para terminar a recursão
Aqui está uma maneira estranha e, normalmente, não é o ideal de fazê-lo, mas hey, ele funciona, e não usar recursividade: -)
void permutations(char c[], int l) // l is the length of c
{
int length = 1;
while (length < 5)
{
for (int j = 0; j < int(pow(double(l), double(length))); j++) // for each word of a particular length
{
for (int i = 0; i < length; i++) // for each character in a word
{
cout << c[(j / int(pow(double(l), double(length - i - 1))) % l)];
}
cout << endl;
}
length++;
}
}
Eu sei que você tem um perfeitamente boa resposta já (os múltiplos na verdade), mas eu estava pensando um pouco sobre este problema e eu vim com um algoritmo bastante elegante que eu poderia muito bem share.
Basicamente, você pode fazer isso, começando com uma lista dos símbolos, e em seguida anexando cada símbolo para o outro símbolo para fazer duas palavras símbolo, e depois anexando cada símbolo para cada palavra. Isso pode não fazer muito sentido como essa, então aqui está o que parece:
Comece com 'a', 'b' e 'c' como os símbolos e adicioná-los a uma lista:
a
b
c
Append 'a', 'b' e 'c' para cada palavra na lista. A lista, em seguida, se parece com:
a
b
c
aa
ab
ac
ba
bb
bc
ca
cb
cc
Em seguida, acrescentar 'a', 'b' e 'c' para cada nova palavra na lista assim que a lista será parecido com este:
a
b
c
aa
ab
ac
ba
bb
bc
ca
cb
cc
aaa
aab
aac
aba
abb
... and so on
Você pode fazer isso facilmente usando um iterador e deixar o iterador manter indo desde o início.
Este código imprime cada palavra que é adicionado à lista.
void permutations(string symbols)
{
list<string> l;
// add each symbol to the list
for (int i = 0; i < symbols.length(); i++)
{
l.push_back(symbols.substr(i, 1));
cout << symbols.substr(i, 1) << endl;
}
// infinite loop that looks at each word in the list
for (list<string>::iterator it = l.begin(); it != l.end(); it++)
{
// append each symbol to the current word and add it to the end of the list
for (int i = 0; i < symbols.length(); i++)
{
string s(*it);
s.push_back(symbols[i]);
l.push_back(s);
cout << s << endl;
}
}
}
Um exemplo Python:
import itertools
import string
characters = string.ascii_lowercase
max_length = 3
count = 1
while count < max_length+1:
for current_tuple in itertools.product(characters, repeat=count):
current_string = "".join(current_tuple)
print current_string
count += 1
A saída é exatamente o que você espera obter: a b c aa ac ab aaa AAB AAC aba abb abc aca acb acc baa bab ... (O exemplo é a utilização dos caracteres ASCII todo minúsculas definido, alteração "caracteres = [ 'a', 'b', 'c']" para reduzir o tamanho de saída)
O que você quer é chamado Permutation.
Verifique isso por um Permutation implementação em java