尋找一個元組替換算法

在訪談中我被問到了這個問題。我知道這是一個組合問題，但我不知道如何遞歸解決這個問題。我主要是在尋找解決這些問題的方法。尋找一個元組替換算法

給定一個元組，例如： (a, b, c)

輸出：
(*, *, *), (*, *, c), (*, b, *), (*, b, c), (a, *, *), (a, *, c), (a, b, *), (a, b, c) 

2012-07-31 mousey

是任何意義的順序？ – Logan 2012-07-31 18:04:13

如果用星號替換星號並將星號替換爲1，則這會變成二進制數字。這可能會給你一些關於如何實現它的想法。 – Kevin 2012-07-31 18:05:23

問題陳述是否表明您需要遞歸解決這個問題？最明顯的解決方案很容易在'for'循環中編碼。 – steveha 2012-07-31 18:45:50

這是使用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-31 19:12:50 ecatmur

實現該特定問題的一種簡單的方法：對於n進制元組，從0到2^N只是環 - 1，以及用於在它們之間的每個整數，如果第k個二進制數字是1，則元組中的第k個位置是元組中的原始元素;如果這個數字是0，那麼第k個位置是*。

當然，這種方法會很容易溢出，而且不是遞歸的;然而，它可以平凡地重寫成一個遞歸程序（只是遞歸探索每個二進制數字）。

來源

2012-07-31 18:05:29

你需要大量的元素來溢出這個方法嗎？ – 2012-07-31 18:37:49

假設訂單是無關的，在這裏你去。我使用了一個內部字符串來實現它更容易。該代碼也適用於n的任何n元組數組，它是一個正整數。

有關此實現的一些解釋：將基本情況設置爲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-31 18:40:04 clwen

我認爲如果你將基本情況改爲'['*'，s]'，並且在'_combinations'中反轉兩個'output.append'行，那麼你的輸出將與OP的排序相同。 – Kevin 2012-07-31 18:56:30

@凱文不完全。它將是（a，b，*），（*，b，*），（a，*，*），（*，*，*），（a，b，c），（*，b，c ），（a，*，c），（*，*，c）'。 IMO的命令在這個問題上並不重要。但是，如果訂單確實重要，只需根據組合生成後的任何標準對其進行排序即可。 – clwen 2012-07-31 18:59:47

類似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-31 18:54:31 Kevin

每涉及二進制計數（比組合要好得多的解決方案一些恕我直言）

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

不錯，又短又快...它笑uld處理多達32個（或者大的整數是...甚至可能更大，因爲Python使用任意大的整數）

來源

2012-07-31 19:05:08

你可以解釋一下bin_template如何生成二進制數字。 – mousey 2012-08-01 00:06:33

它只是設置一個新的樣式格式字符串，它告訴它是二進制的，0（左）填充到列表中的許多元素。「{0：03b}」在示例中的元組爲000 = 0,001 = 1,010 = 2等。但我認爲ecatmur的答案更好 – 2012-08-01 01:37:25

感謝您的回覆 – mousey 2012-08-02 02:21:08

由於這是一個面試問題，面試官可能在尋找理解遞歸原則，因爲這通常是這些組合問題的出發點。

這個怎麼樣代碼，表明您明白：

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-01 17:23:57

尋找一個元組替換算法

回答

相關問題