基数 3 の組み合わせ論における順列の数を計算するにはどうすればよいですか?

StackOverflow https://stackoverflow.com/questions/447783

  •  22-07-2019
  •  | 
  •  

質問

私は数学があまり好きではなかったので、誰かが次の点で私を助けてくれることを願っています。

私は5つの箱を持っています： 

 1   2   3   4   5
[ ] [ ] [ ] [ ] [ ]

ボックスは白、グレー、または黒のいずれかになります (または 0、1、2 と考えることができます)。

ボックス セットはいくつの状態を取ることができますか?

考えられるすべての結果を生成するための疑似コード (または任意の言語) は何ですか??

つまり...

00000
00001
00011
00111

などなど...

これに関して誰かが私に助けてくれることに本当に感謝しています。

役に立ちましたか？

解決

これは古典的な順列生成の問題です。各ポジションには3つの可能性があり、5つのポジションがあります。生成される文字列の総数は3 ^ 5 = 243です。 一般的な解決策が必要な場合は、再帰が必要です（単純な反復ループは、問題の単一のインスタンスに対してのみ機能します）。

簡単な例を次に示します。

public static void Main(string[] args){

    Generate("", 5);
}

private void Generate(string s, int limit)
{
    if (s.Length == limit)
        Console.WriteLine(s);
    else
    {
        Generate(s+"0", limit);
        Generate(s+"1", limit);
        Generate(s+"2", limit);
    }
}

他のヒント

組み合わせの数に対する答えは、3x3x3x3x3（3 ^ 5）です。これは、各ボックスに3色が可能なためです。

結果の生成に関しては、ボックスの色を表すために0、1、または2を使用してこのマトリックスを使用してそれを把握できるかどうかを確認してください。小規模（3つのボックスを想定）では、次のようになります：

0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
0 2 0
0 2 1
0 2 2
1 0 0
1 0 1
1 0 2
1 1 0
1 1 1
1 1 2
1 2 0
1 2 1
1 2 2
2 0 0
2 0 1
2 0 2
2 1 0
2 1 1
2 1 2
2 2 0
2 2 1
2 2 2

最初の質問に答えるために、ボックスに 2 つの値のうち 1 つだけを含めることができる場合、答えは何になるでしょうか?では、ボックスに 3 つの値のいずれかが含まれている場合、答えは何でしょうか?

2 番目の質問に答えるには、1 つのボックスで考えられるすべての結果を生成する疑似コードは何ですか?さて、疑似コードは 2 つのボックスの考えられるすべての結果を生成しますか?

最初に紙で問題を解決することをお勧めします。少ない数のボックス（おそらく3つ）で解決し、すべての可能性をリストしてください。次に、あなたの推論がどのように進んだか、または小さな子供に何をしたかをどのように説明するかを考えます。

少なくとも、実際に私に答えてくれたあなたの答えに感謝します。

質問はComputer Science 101からまっすぐに引き出されたように聞こえたが、そうではなかったことは理解できる。皮肉なことに、それは実際の締め切りの現実の生活のためであり、私がこのことを教えられていて、「このがらくたが必要になるのはいつか」と言われたときを思い出す時間がありませんでした;

私が小学生のように愛護され、扱われたい場合、小学校に戻って小学5年生の先生にトイレに行けるかどうか 尋ねます

ありがとうございます

状態の数は3 ^ 5です。

擬似コードは

for value from 0 to 3^5-1
    print base3(value)

ここで、base3は、3を法として繰り返して数字を取得し、その数字を削除する（3で除算する）関数です

ヒント：各ボックスは数字の位置であり、各色は異なる数字であると想像してください。現実の世界では、2桁と10桁の数字でいくつの組み合わせ（ゼロを含む）が得られますか？ 3ポジションはどうですか？使用可能な桁数を考慮して、余分な位置の追加と組み合わせの数の関係はどうですか？

固有の組み合わせの数： 3 ^ 5 = 243

コード：

n = 0
for i = 0 to 3^5-1
{
    s = ""
    for j = 1 to 5
    {
        d = n mod 3
        s = toascii(d) . s
        n = n / 3
    }
    println s
    i = i + 1
}

これを行うことを最初に学んだ方法は次のとおりです。まず、選択する選択肢の数について考えます。各ボックスに1つずつ、5つの選択を行っています。したがって、乗算記号を使用して5行の空白行を書き留めます。

__ x __ x __ x __ x __ = ?

各空白に、そのボックスから選択する必要があるオブジェクトの数を記入します。ボックスごとに3つの数字を選択できるため、すべての空白に3を入力します。

3 x 3 x 3 x 3 x 3 = 243

これにより、それらの選択肢の順列の総数が得られます。

可能性の数は3の5乗です

0からその数値から1を引いた値までループし、それを基数3で表現すると、すべての可能性があります（必要に応じて0を追加することを忘れないでください）

Rubyの場合：

number_of_possibilities = 3**5-1

for i in (0..number_of_possibilities)
  base_3_number = i.to_s(3)
  puts "%05d" % base_3_number # number formatting used to prepend 0s where necessary
end

これについてあなたが理解していないことや、あなたがつまずいたことについて尋ねることはできますか？ここの誰もが単に質問に答えているようですが、答えをコピーした場合は何も学ばないため、宿題のポイントを完全に逃してしまいます。次のレッスンがこのレッスンに基づいていると仮定すると、あなたはさらに遅れをとります。

あなたが私のために働いていた場合、または私のクラスにいた場合、私は単に以下を尋ねるでしょう...

＆quot;問題はどのように解決すべきだと思いますか？＆quot;ハングアップしている場所を明らかにする答え。 CMUの私の賢明な教授はかつて「あなたが理解していないことを理解するまでこれを理解するのを助けることはできません」と言いました。理解できなかったことを理解できなかったので、彼のクラスを落としましたが、レッスンは固執しました。

おそらく遅すぎることはわかっていますが、これらの宿題の質問については、単に答えを提供して宿題をするのではなく、その人が学ぶのを助けるべきだと思います。

あなたの問題は、コンビナトリクスの製品のルールのみを必要とします。

最初のボックスの状態を3つの方法で選択でき、 2番目のボックスの状態を3つの方法で選択できます。 3つの方法で5番目のボックス。すべてのボックスの状態を設定できるウェイの数は、5つの（等しい）ウェイの数すべての積、つまり3x3x3x3x3 = 3 5 です。

同様の質問：10進法で5桁の数字をいくつ作成できますか？つまり、00000から99999までの数字はいくつありますか？最初の桁を10通りの方法（0 ... 9）などで選択できます。既にわかっているように、答えは10x10x10x10x10 = 100000です。

これは宿題の問題のようです。その解決策についてのヘルプを提供します。

あなたが言っているのは、各ボックスには3つの状態があり、それらはすべて独立しているということです。 1つのボックスには3つのソリューションがあり、2つのボックスには3 * 3のソリューションがあります。最初のボックスの各状態に対して、2番目のボックスにも3つの状態があります。それを5つのボックスに拡張します。

各ソリューションを生成するには、それを循環するだけです。各ボックスにforループをネストするのは簡単です。10の累乗を掛けると、一度に数を表示できます。

同様の方法で複数のボックスのコードを一般化できます。

これに答えるためのコードを書こうとさえしないでください！理由は、それを計算するために非常に大きな数（階乗）が必要だからです。これらは、CLRのどの基本型よりもはるかに大きな数を作成します。このオープンソースライブラリを使用して計算を行うことができます。

void solve(int p=0,int n=5,int d=0)
{
    if (n==p)
    {
        int rev=d;
        int i=0;
        while (i<5) {
            cout << rev%10;
            rev /= 10;
            i++;## Heading ##
        }
        cout << endl;
        return;
    }
    for(int i=0; i<3 ; i++)
    {
        solve(p+1,n, d*10 + i);
    }
}
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top