1

面接でこんな質問をされました。組み合わせの問題であることはわかっていましたが、これを再帰的に解決する方法がわかりません。私は主に、この種の問題を解決するためのアプローチを探しています。

たとえば、タプルが与えられます。(a, b, c)

出力:

(*, *, *), (*, *, c), (*, b, *), (*, b, c), (a, *, *), (a, *, c), (a, b, *), (a, b, c)
4

6 に答える 6

5

これは、次を使用した簡単なワンライナーitertools.productです。

list(itertools.product(*(('*', x) for x in seq)))

これにより、要求されたのと同じ順序が得られます。

>>> list(itertools.product(*(('*', x) for x in "abc")))
[('*', '*', '*'), ('*', '*', 'c'), ('*', 'b', '*'), ('*', 'b', 'c'), ('a', '*', '*'), ('a', '*', 'c'), ('a', 'b', '*'), ('a', 'b', 'c')]
于 2012-07-31T19:12:50.277 に答える
1

この特定の問題を実装する簡単な方法: n 項タプルの場合、0 から 2^n - 1 までループし、その間の各整数について、k 番目の 2 進数が 1 の場合、k 番目の位置in the tuple はタプルの元の要素です。その桁が 0 の場合、k 番目の位置は * です。

もちろん、このメソッドはオーバーフローしやすく、再帰的ではありません。ただし、再帰プログラムに簡単に書き直すことができます (すべての 2 進数を再帰的に探索するだけです)。

于 2012-07-31T18:05:29.677 に答える
1

clwenの答えに似ていますが、組み合わせ問題に適したジェネレータ関数を使用しています:

def combinations(seq):
    if len(seq) == 1:
        yield ('*',)
        yield (seq[0],)
    else:
        for first in combinations([seq[0]]):
            for rest in combinations(seq[1:]):
                yield first + rest

print list(combinations("abc"))

出力:

[('*', '*', '*'), ('*', '*', 'c'), ('*', 'b', '*'), ('*', 'b', 'c'), 
('a', '*', '*'), ('a', '*', 'c'), ('a', 'b', '*'), ('a', 'b', 'c')]
于 2012-07-31T18:54:31.520 に答える
1

順番は関係ないと思いますが、どうぞ。実装を容易にするために内部文字列を使用しました。このコードnは、正の整数である任意の n タプル配列に対しても機能します。

この実装に関するいくつかの説明: 基本ケースを 1 タプル (私の実装では、長さ 1 の文字列) として設定します。この場合、戻り値*と引数の内容。*それ以外の場合は、現在の要素を現在の要素の内容で置き換えることにより、再帰で 1 つの要素を進めます。

上記のアルゴリズムに従って決定木を描いていただけるとわかりやすいと思います。

def _combination(s):
    if len(s) == 1:
        return ['*', s]
    else:
        rest = _combination(s[1:])
        output = []
        for r in rest:
            output.append('*' + r)
            output.append(s[0] + r)
        return output

def combination(t):
    s = ''.join(c for c in t)
    result = _combination(s)
    output = []
    for r in result:
        output.append(format_tuple(r))
    print ', '.join(output)

def format_tuple(s):
    return '(' + ', '.join(s) + ')'

if __name__ == '__main__':
    t = ('a', 'b', 'c')
    combination(t)

プログラムの出力:

(*, *, *), (a, *, *), (*, b, *), (a, b, *), (*, *, c), (a, *, c), (*, b, c), (a, b, c)

ケビンのコメントに従って更新されました。

于 2012-07-31T18:40:04.930 に答える
1

バイナリカウントを含むソリューションごと（コンボのものよりもはるかに優れています）

t_str = raw_input("Enter Tuple Values Separated By Spaces:")
t = t_str.split()
n = len(t)
bin_template = "{0:0"+str(n)+"b}"
for i in range(2**n):
    bval = bin_template.format(i)
    solution= "("+",".join(["*" if bval[i] == "0" else t[i] for i in range(n)])+")"
    print solution

素敵で短くて速い...そして、最大32までの任意のサイズのタプルを処理する必要があります（または、大きなintは...そして、Pythonは任意に大きな整数を使用するため、さらに大きいかもしれません）

于 2012-07-31T19:05:08.197 に答える
0

これはインタビューの質問だったので、インタビュアーは再帰の原則の理解を求めているかもしれません。なぜなら、それは一般的にこの種の組み合わせに関する質問の出発点だからです。

このコードはどうですか、それを理解していることを示すために：

def generate(x, state, level):
    if level == len(x):
        print state
    else:
        state[level] = '*'
        generate(x, state, level+1)
        state[level] = x[level]
        generate(x, state, level+1)


if __name__ == '__main__':
    x = [ 'a','b','c']
    generate(x,['*','*','*'], 0)
于 2012-08-01T17:23:57.933 に答える