4

特定のセットの可能な組み合わせをすべて取得する必要があります。たとえば、[1, 4, 7] の場合、結果の組み合わせは次のようになります。

  • 111, 114, 117, 141, 144, 147, 171, 174, 177, 411, 414, 417, 441, 444, 447, 471, 474, 477, 711, 714, 717, 741, 744, 747, 771, 774、777。

メソッドを使用してみnext_permutationましたが、それは私が望むものではありません (これは 111、144、717 などの値を返しません)。

C++でこれを行う方法はありますか？完全な初心者ですのでご了承ください。

前もって感謝します。

4

7 に答える 7

8

数字をよく見てください。リストしたすべての数字は、リスト{11,14,17,41,44,47,71,74,77}の前に1を付け、1回は4を、もう1回は7として表すこともできます。 。これは一般的なルールを示しています。

セット{1,4,7}の3つの数字を持つ文字列は、同じセットの2つの数字を持つ文字列を取得し、セットの各要素の前に付けることによって作成されます。

このルールの3と2を一般化し、結果のアイデアを再帰的に実装すると、問題のアルゴリズムが得られます。

C ++の実装上の注意として、数値を表すために整数ではなく文字列を使用するようにしてください。この問題は算術ではなく、基数10の表現と密接に関連しています。文字列はあなたの生活をはるかに楽にします。

于 2012-04-25T12:41:28.710 に答える
1

vectorセット内の要素の数と同じサイズの整数のベクトル ( と呼ばれる) を作成します。各エントリを 0 に初期化します。次に、次のアルゴリズムに従います。

1) Walk vector、対応する要素を出力します。(したがって、ベクトルが 0,1,1 で集合が [9,8,7] の場合、出力 988 -- ゼロ番目の要素、最初の要素、最初の要素)。

2) 呼び出される整数elementを 0 に設定します。

3) インクリメントvector[element]. vector[element]セット内の要素の数と等しいかどうかを確認します。そうでない場合は、ステップ 1 に進みます。

4)vector[element]ゼロに設定します。増分しelementます。elementセット内の要素の数より少ない場合は、手順 3 に進みます。

5) 停止します。これで完了です。

于 2012-04-25T12:38:32.570 に答える
1

{1, 4, 7} などの値で配列を作成します。

ループには length(array) を使用し、それぞれに length(array) 反復があります。

最も内側のループ出力 100 * array[i] + 10 * array[j] + array[k]


最大長がわからない場合は、代わりに再帰を使用します。たとえば、疑似コード:

void Solve(int[] array, int length, int position, int sum)
{
    position++;
    sum *= 10;

    for (int cnt = 0; cnt < length; cnt++)
    {
        int tempsum = sum + array[cnt];

        if (position == length)
            output(tempsum);
        else
            Solve(array, length, position, tempsum);
    }
}
于 2012-04-25T12:33:02.163 に答える
0

000から222までの3を底として効果的に数え、それらの数字をインデックスとして[1、4、7]の配列を検索します。これを一般化して、任意のサイズの入力配列で機能するようにします。

int n = digits.size();
int n_n = std::pow(n, n);
for (int i = 0; i < n_n; ++i)
{
     int x = i;
     for (int j = 0; j < n; ++j)
     {
          cout << digits[x % n];
          x /= n;
     }
     cout << ' ';
}
于 2012-04-25T13:40:07.083 に答える
0

さて、私は自由にタスクを実装しようとしました。アルゴリズムの知識を少し減らしたかったのです。次のようになりました。

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

vector<int> allowedNumbers;

bool my_next_perm(vector<int>::iterator& begin, vector<int>::iterator& end) {
    for (vector<int>::iterator itr = end - 1; ; --itr)
    {
        if (*itr != allowedNumbers.back())
        {
            *itr = *upper_bound(allowedNumbers.begin(), allowedNumbers.end(), *itr);
            while ((++itr) != end) {
                *itr = allowedNumbers[0];
            }
            return true;
        }
        if (itr == begin)
        {
            return false;
        }
    }
}
void printAllPermutationsWithRepetitions(vector<int>& v)
{
    int n = v.size();
    set<int> allNumbers;
    for (int i = 0; i < n; i++)
    {
        allNumbers.insert(v[i]);
    }
    for (set<int>::iterator itr = allNumbers.begin(); itr != allNumbers.end(); ++itr) {
        allowedNumbers.push_back(*itr);
    }
    for (int i = 0; i < n; i++) {
        v[i] = allowedNumbers[0];
    }

    do {
        for (int i = 0; i < n; i++) {
            if (i != 0) cout << " ";
            cout << v[i];
        }
        cout << endl;
    } while(my_next_perm(v.begin(), v.end()));
}

int main (int argc, char *argv[]) {
    vector<int> v;
    v.push_back(7);
    v.push_back(1);
    v.push_back(3);
    printAllPermutationsWithRepetitions(v);
    return 0;
}

実装はわずかに最適ではありません (私が使用しているためupper_bound)。

于 2012-04-25T12:47:24.643 に答える
0

ここで私の答えを見てください：PHPはすべての組み合わせを取ります

ヒント :これは C++ コードではありませんが、アイデアは理解できるでしょう。（再帰を使用することをお勧めします）

于 2012-04-25T12:35:18.807 に答える