2

シーケンス [1,2,3] を検討します。このシーケンスには、[1] と [2] と [3] と [1,2] と [2,3] と [1,2,3] の 6 つの異なるシーケンスがあります。

ノート！最初のシーケンスの長さは最大 100 桁です。私を助けてください。次のシーケンスを作成するにはどうすればよいですか? この種のアルゴリズムについてもっと研究するのが大好きです。この種のアルゴリズムの名前を教えてください。

4

3 に答える 3

1

すべてのサブ シーケンスを出力するためのコードは次のとおりです。アルゴリズムはネストされたループを使用します。

    #include<stdio.h>

  void seq_print(int A[],int n)
{
    int k;
    for(int i =0;i<=n-1;i++)
    {
        for(int j=0;j<=i;j++)
        {
            k=j;
            while(k<=i)
            {
                printf("%d",A[k]);
                k++;

            }
            printf("\n");
        }
}

}

void main()
{
    int A[]={1,2,3,4,5,6,7,8,9,0};
    int n=10;
    seq_print(A,n);

}
于 2013-03-23T08:04:07.387 に答える
0

あなたの問題は、組み合わせの問題に減らすことができます。stackoverflow には、すでに多くのソリューションが存在します。あなたはこれをチェックすることができます、それはあなたにとって役に立つかもしれません.

于 2013-03-24T13:40:23.863 に答える
0

それはパワーセットと呼ばれます（あなたの場合、空のセットは除外されます）。

パワー セットを構築するには、空のセットを含むセットから始めます。次に、入力セットの各アイテムに対して、現在のアイテムが含まれているこれまでに蓄積されたすべてのサブセットでパワーセットを拡張します (Python の場合):

def powerset(lst):
    S = [[]]
    for item in lst:
        S += [subset + [item] for subset in S]
    return S

例：

print(powerset([1, 2, 3]))
# -> [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

一度にすべてのサブセットを生成することを避けるために、再帰的な定義を使用できます。

  • 空集合の冪集合は空集合を含む集合である
  • アイテムを含むセットのパワー セットには、nアイテムを含むセットのパワー セットからのn - 1すべてのサブセットと、n-th 番目のアイテムが含まれるこれらすべてのサブセットが含まれます。
def ipowerset(lst):
    if not lst: # empty list
        yield []
    else:
        item, *rest = lst
        for subset in ipowerset(rest):
            yield subset
            yield [item] + subset

例：

print(list(ipowerset([1, 2, 3])))
# -> [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

パワー セットを生成するさらに別の方法は、ゼロから入力セット (レシピ)のサイズまでrすべての長さのサブシーケンス (組み合わせ)を生成することです。ritertools

from itertools import chain, combinations

def powerset_comb(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

例：

print(list(powerset_comb([1, 2, 3])))
# -> [(), (1,), (2,), (3,), (1,2), (1,3), (2,3), (1,2,3)]

セットを組み合わせる良い方法は何ですか？.

于 2013-03-25T03:53:13.633 に答える