2008-12-27 138 views
1

我有一個字符串(無限長度),我想複製很多次,每次從字符數組(字符長度)替換一個字符。替換數組中的字符串

所以說我有這個字符串: 'AA'
這陣:[ '一', 'B', 'C', 'd']

一些魔術後套住的東西會有是'aa','ab','ac','ad','ba','bb'...'dc','dd']

你會怎麼做?我嘗試了三個for循環,但我似乎無法得到它。

編輯
上字符串的依賴性如下:

說出字符串是: 'BA'
則輸出應該是:[ 'BA', 'B-B', 'BC' ,'bd','ca'...'dd']

回答

2

如果字符串的結果數組中的順序並不重要,從最初的字符串中的所有字符都替換陣列中,則:

#!/usr/bin/env python 
from itertools import product 

def allreplacements(seed, replacement_chars): 
    assert all(c in replacement_chars for c in seed) 
    for aset in product(replacement_chars, repeat=len(seed)): 
     yield ''.join(aset) 

print(list(allreplacements('ba', 'a b c d'.split()))) 
# ['aa', 'ab', 'ac', 'ad', 'ba', 'bb', 'bc', 'bd', 'ca', 'cb', 'cc', 
# 'cd', 'da', 'db', 'dc', 'dd'] 

下面是一個根兒的溶液al case。置換是在詞典順序進行:

#!/usr/bin/env python 
from itertools import product 

def allreplacements(seed, replacement_chars): 
    """Generate all possible replacements (with duplicates).""" 
    masks = list(product(range(2), repeat=len(seed))) # e.g., 00 01 10 11 
    for subs in product(replacement_chars, repeat=len(seed)): 
     for mask in masks: 
      # if mask[i] == 1 then replace seed[i] by subs[i] 
      yield ''.join(s if m else c for s, m, c in zip(subs, mask, seed)) 

def del_dups(iterable): 
    """Remove duplicates while preserving order. 

    http://stackoverflow.com/questions/89178/in-python-what-is-the-fastest-algorithm-for-removing-duplicates-from-a-list-so#282589 
    """ 
    seen = {} 
    for item in iterable: 
     if item not in seen: 
      seen[item] = True 
      yield item 

print(list(del_dups(allreplacements('ba', 'abcd')))) 
print(list(del_dups(allreplacements('ef', 'abcd')))) 
# ['ba', 'aa', 'bb', 'ab', 'bc', 'ac', 'bd', 'ad', 'ca', 'cb', 'cc', 
# 'cd', 'da', 'db', 'dc', 'dd'] 

# ['ef', 'ea', 'af', 'aa', 'eb', 'ab', 'ec', 'ac', 'ed', 'ad', 'bf', 
# 'ba', 'bb', 'bc', 'bd', 'cf', 'ca', 'cb', 'cc', 'cd', 'df', 'da', 
# 'db', 'dc', 'dd'] 
0

如果字符串和數組都不包含'a',問題會更清楚。所需的輸出不顯示對輸入字符串的任何依賴。

+0

謝謝,我澄清的我的問題 – 2008-12-27 23:09:41

0

嗯,兩個for循環應該這樣做:Python的pseudocode--

a = "abcd" 
b = "ba" 
res = [] 
for i in a:   # i is "a", "b", ... 
    for j in b:   # j is "b", "a" 
     res.append(i+j) # [ "ab", "bb",...] 
return res 

[更新:啞錯字改正]

+0

您的意思是'res.append(I + J)`?這是錯誤的。結果字符串始終以`b`中的字符結尾。 – jfs 2008-12-28 00:38:50

+0

是的,謝謝,糾正。結果字符串始終以b中的一個字符結尾。 – 2008-12-28 01:33:03

0

您可以使用下面的代碼在兩個方面:

  1. 讓所有字符串作爲一個數組
  2. 牽線一次一個

對於使用(1),請調用getStrings()方法(根據需要多次)。

如果使用(2),請致電next()方法只有只要hasNext()返回true。 (實現一個reset()方法作爲練習留給讀者!;-)

package com.so.demos; 

import java.util.ArrayList; 
import java.util.List; 

public class StringsMaker { 

    private String seed; // string for first value 
    private char[] options; // allowable characters 

    private final int LAST_OPTION; // max options index 
    private int[] indices;   // positions of seed chars in options 
    private int[] work;    // positions of next string's chars 
    private boolean more;   // at least one string left 

    public StringsMaker(String seed, char[] options) { 
     this.seed = seed; 
     this.options = options; 
     LAST_OPTION = options.length - 1; 
     indices = new int[seed.length()]; 
     for (int i = 0; i < indices.length; ++i) { 
      char c = seed.charAt(i); 
      for (int j = 0; j <= LAST_OPTION; ++j) { 
       if (options[j] == c) { 
        indices[i] = j; 
        break; 
       } 
      } 
     } 
     work = indices.clone(); 
     more = true; 
    } 

    // is another string available? 
    public boolean hasNext() { 
     return more; 
    } 

    // return current string, adjust for next 
    public String next() { 
     if (!more) { 
      throw new IllegalStateException(); 
     } 
     StringBuffer result = new StringBuffer(); 
     for (int i = 0; i < work.length; ++i) { 
      result.append(options[work[i]]); 
     } 
     int pos = work.length - 1; 
     while (0 <= pos && work[pos] == LAST_OPTION) { 
      work[pos] = indices[pos]; 
      --pos; 
     } 
     if (0 <= pos) { 
      ++work[pos]; 
     } else { 
      more = false; 
     } 
     return result.toString(); 
    } 

    // recursively add individual strings to result 
    private void getString(List<String> result, int position, String prefix) { 
     if (position == seed.length()) { 
      result.add(prefix); 
     } else { 
      for (int i = indices[position]; i < options.length; ++i) { 
       getString(result, position + 1, prefix + options[i]); 
      } 
     } 
    } 

    // get all strings as array 
    public String[] getStrings() { 
     List<String> result = new ArrayList<String>(); 
     getString(result, 0, ""); 
     return result.toArray(new String[result.size()]); 
    } 

}