1

たとえば、5文字のアルファベットがあると想像してください: ABCDE。

これらの文字の 3 つの可能なセットをすべて列挙したいと思います。各文字はセットに 1 回しか存在できず、文字の順序は関係ありません (したがって、セット内の文字はソートする必要があります)。

したがって、次のセットを取得します。

  1. ABC
  2. ABD
  3. 阿部
  4. ACD
  5. エース
  6. ADE
  7. BCD
  8. 紀元前
  9. BDE
  10. CDE

全部で10セット。順序は辞書順です。

ここで、アルファベットの長さがN(この例では 5)、セットの長さがM(この例では 3) であるとします。Nとを知ってMいれば、可能な場合はどうすればよいでしょうか。

  1. 最悪の組み合わせの総数を教えてくださいO(M+N)(この例では答えは 10 です)。
  2. 与えられた数字 (1 の場合は ABC を返し、5 の場合は ACE を返すなど) の組み合わせを最悪で出力しO(M+N)ますか?

リスト全体を生成することで複雑なことを行うのは簡単O(M^N)ですが、もっと良い解決策があるのではないかと思います。

4

2 に答える 2

1

最初の質問への答えは簡単です: それは、 size のセットからアイテムC(n,r)のすべての組み合わせを選択する場所です。式は他の場所の中でもここにあります：rn

C(n,r) = n! / (r! (n-r)!)

他のすべてを計算せずに組み合わせを選択できるかi'thどうかは、組み合わせ番号を組み合わせに関連付けるエンコーディングに依存しiます。それははるかに困難であり、より多くの考えが必要になります...

（編集）

この問題をさらに考えてみると、解決策は Python では次のようになります。

from math import factorial

def combination(n,r):
    return factorial(n) / (factorial(r) * factorial(n-r))

alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

def showComb(n,r,i,a):
    if r < 1:
        return ""
    rr = r-1
    nn = max(n-1,rr)
    lasti = i
    i -= combination(nn,rr)
    j = 0
    while i > 0:
        j += 1
        nn = max(nn-1,1)
        rr = min(rr,nn)    # corrected this line in second edit
        lasti = i
        i -= combination(nn,rr)
    return a[j] + showComb(n-j-1,r-1,lasti,a[(j+1):])

for i in range(10):
    print(showComb(5,3,i+1,alphabet))

...質問に示されているリストを出力します。

私が使用したアプローチはi'th、残りのセット要素の組み合わせの数を使用して、特定の番号の最初の要素であるべき要素を見つけることができるという考えを使用して、出力セットの最初の要素を見つけることiです。

つまり、C(5,3) の場合、最初の C(4,2) (=6) 出力セットは最初の文字として 'A' を持ち、次の C(3,1) (=3) 出力セットは'B' then C(1,1) (=1) セットの最初の文字は 'C' です。

次に、関数は残りの要素を再帰的に見つけます。は末尾再帰であるため、必要に応じてループとして表現することもできますshowComb()が、この場合は再帰バージョンの方が理解しやすいと思います。

さらにテストするには、次のコードが役立つ場合があります。

import itertools

def showCombIter(n,r,i,a):
    return ''.join(list(itertools.combinations(a[0:n],r))[i-1])

print ("\n")

# Testing for other cases   
for i in range(120):
    x = showComb(10,3,i+1,alphabet)
    y = showCombIter(10,3,i+1,alphabet)
    print(i+1,"\t",x==y,"\t",x,y)

...これにより、このケースの 120 例すべてが正しいことが確認されました。

時間の複雑さを正確に計算していませんが、呼び出しの数はshowComb()になりr、whileループはn1 回またはそれ以下で実行されます。factorial()したがって、質問の用語では、関数が一定時間で計算できると仮定すると、複雑さは O(M+N) 未満になると確信しています。その実装は単純です。

于 2013-03-30T03:09:10.210 に答える
0

最初の部分は簡単だと思います。これと同様の方程式を、選択した言語に代入してください。

x=12
y=5
z=1
base=1
until [[ $z -gt y ]]
do
 base=`echo $x $z $base|awk '{print ($1/$2) * $3}'`
 x=`expr $x - 1`
 z=`expr $z + 1`
 echo base:$base
done

echo $base

上記の例では、792 通りの組み合わせで 5 個のセットに配置された 12 個のアイテムを使用しています。

質問の 2 番目の部分を実行するには... 考えているところですが、簡単にはいきません。

于 2013-03-30T04:51:13.810 に答える