1

我有一个字符串（长度不足），我想复制很多次，一次从字符数组（长度不足）中替换一个字符。

所以说我有这个字符串：'aa'
这个数组：['a', 'b', 'c', 'd']

在一些神奇的for循环之后会有一个数组，如： ['aa', 'ab', 'ac', 'ad', 'ba', 'bb' ... 'dc', 'dd']

你会怎么做？我尝试了使用三个 for 循环的东西，但我似乎无法得到它。

编辑
对字符串的依赖如下：

假设字符串是：'ba'，
那么输出应该是：['ba', 'bb', 'bc', 'bd', 'ca' ... 'dd']

4

4 回答 4

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']

这是一般情况的解决方案。替换按字典顺序执行：

#!/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']
于 2008-12-28T00:40:14.367 回答
0

如果字符串和数组不都包含“a”，问题会更清楚。所需的输出不显示对输入字符串的任何依赖性。

于 2008-12-27T23:06:58.097 回答
0

嗯，应该有两个 for 循环：Python 伪代码——

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

[更新：纠正了愚蠢的错字。]

于 2008-12-28T00:12:47.280 回答
0

您可以通过两种方式使用以下代码：

  1. 将所有字符串作为一个数组
  2. 一次拉一根弦

对于用法 (1)，调用该getStrings()方法（根据需要多次）。

对于用法 (2)，只要返回true ，就调用该next()方法。（实现一个方法留给读者作为练习！;-)hasNext()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()]);
    }

}
于 2008-12-28T01:48:46.273 回答