3
  • 潜在的な読者の時間と健康を節約するために、元のテキストを編集しました。多分誰かがこれを実際に使用するでしょう。

私はそれが基本的なものであることを知っています。おそらく非常に基本的なものです。
指定されたセットのすべての可能な組み合わせを取得する方法。例
string set = "abc";
abc aa ab ac aaa aab aac aba abb
abc aca acb acc baa bab ...
そしてリストは続きます (長さの制限が設定されていない場合)。

そのための非常にきれいなコードを探しています-私が見つけたのは、ちょっと汚れていて正しく機能していませんでした。私が書いたコードについても同じことが言えます。

複数のスレッドで動作するブルート フォース (md5) 実装を作成しているため、このようなコードが必要です。パターンは、スレッドに独自の組み合わせのチャンクを供給する親プロセスがあるため、これらは独自に処理します。
例: 最初のスレッドは 100 個の順列のパッケージを取得し、2 番目のスレッドは次の 100 個を取得します
。最終的なプログラムをどこかに投稿する必要があるかどうか教えてください。

EDIT #2 もう一度、皆さんに感謝します。
あなたのおかげで、私は MPICH2 で実装されたスレーブ/マスター ブルート フォース アプリケーションを完成させました (そうです、Linux やネットワークなどの Windows で動作します)。時間 (そして太陽) 次のタスクに進みます ... :)
StackOverflow コミュニティが素晴らしいことを教えてくれました - ありがとう!

4

8 に答える 8

7

与えられた長さまでの累乗セットの順列を生成する C++ コードを次に示します。

この関数getPowPermsは、一連の文字 (文字列のベクトルとして) と最大長を取り、並べ替えられた文字列のベクトルを返します。

#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';
}

実行すると、この例は出力します

a b c aa ba ca ab bb cb ... acc bcc ccc

更新:これが役立つかどうかはわかりませんがnext、現在のアイテムを指定してリスト内の次のアイテムを作成する「ジェネレーター」関数が呼び出されます。

おそらく、最初のN 個のアイテムを生成してどこかに送信し、次のN 個のアイテムを生成して別の場所に送信することができます。

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 );
  }
}
于 2009-06-13T12:36:25.853 に答える
5

C++ には関数 next_permutation() がありますが、それはあなたが望むものではないと思います。

再帰関数を使用すると、非常に簡単に実行できるはずです。例えば

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])
    }
  }
}

編集:スレッドの部分については、パスワード ブルート フォーサーに取り組んでいると思いますか?

もしそうなら、パスワードのテスト部分は、パスワード生成よりも高速化したいものだと思います。

したがって、すべての組み合わせを生成する親プロセスを作成するだけで、k番目ごとのパスワードがチェックのためにスレッドk mod N ( Nはスレッドの数) に与えられます。

于 2009-06-13T11:47:10.730 に答える
0

あなたはすでに完全に良い答えを持っていることを知っています（実際には複数の答えがあります）が、私はこの問題について少し考えていて、私が共有したほうがよいかなりきちんとしたアルゴリズムを思いつきました。

基本的には、シンボルのリストから始めて、各シンボルを互いに追加して2つのシンボルワードを作成し、次に各シンボルを各ワードに追加することでこれを行うことができます。それはあまり意味がないかもしれないので、次のようになります。

記号として「a」、「b」、および「c」で開始し、それらをリストに追加します。

a
b
c

リスト内の各単語に「a」、「b」、「c」を追加します。リストは次のようになります。

a
b
c
aa
ab
ac
ba
bb
bc
ca
cb
cc

次に、リスト内の新しい各単語に「a」、「b」、および「c」を追加して、リストが次のようになるようにします。

a
b
c
aa
ab
ac
ba
bb
bc
ca
cb
cc
aaa
aab
aac
aba
abb
... and so on

これは、イテレータを使用して簡単に行うことができ、イテレータを最初から続行するだけです。

このコードは、リストに追加された各単語を出力します。

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;
        }
    }
}
于 2009-06-14T04:22:02.460 に答える
0

私はあなたにコードを与えることはできませんが、必要なのは再帰アルゴリズムです ここにいくつかの疑似コードがあります

アイデアは単純で、セット内の各文字列を他のすべての文字列と連結してから、文字列を並べ替えます。小さい文字列をすべてセットに追加し、新しいセットで同じことをもう一度行います。飽きるまで続けてください:)

少し混乱するかもしれませんが、少し考えてみてください;)

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

終了条件がないため、これは明らかにスタックオーバーフローを引き起こします:)再帰を終了するために、好きな条件（セットのサイズなど）をbuild_combinations関数に入れます

于 2009-06-13T11:39:11.670 に答える
0

C ++で質問しましたが、別のバージョンの順列がPythonの標準ライブラリにあります。

http://docs.python.org/library/itertools.html#itertools.permutations

しかし、リストには各文字の不定のシーケンスが含まれているため、それらを順序付けする方法を最初に定義し、アルゴリズムを明確に述べる必要があると思います。

于 2009-06-13T11:12:28.130 に答える
0

これは奇妙で、通常は理想的ではない方法ですが、うまく機能し、再帰を使用しません:-)

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++;
    }
}
于 2009-06-13T12:33:40.070 に答える
0

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

出力はまさにあなたが期待するものです: abc aa ab ac aaa aab aac aba abb abc aca acb acc baa bab ... (この例では ASCII 小文字セット全体を使用しています。"characters = ['a',' b','c']" を使用して、出力のサイズを縮小します)

于 2009-06-14T11:45:13.830 に答える
-1

あなたが望むものは順列と呼ばれます。

Javaでの順列の実装については、これを確認してください

于 2009-06-13T11:04:20.380 に答える