Заменить строковые символы из массива

Question

У меня есть строка (определенной длины), которую я хочу много раз заменять по одному символу за раз из массива (определенной длины) символов.

Так скажи, у меня есть эта строка: 'aa'
И этот массив: ['a', 'b', 'c', 'd']

после некоторой магической циклической работы будет такой массив: ['aa', 'ab', 'ac', 'ad', 'ba', 'bb' ... 'dc', 'dd ']

Как бы вы это сделали? Я пробовал что-то, используя три для циклов, но я просто не могу этого понять.

Редактировать
Зависимость от строки следующая:

Скажите, что строка: 'ba'
тогда вывод должен быть: ['ba', 'bb', 'bc', 'bd', 'ca' ... 'dd']

Answer 1

Если порядок строк в результирующем массиве не имеет значения и все символы из исходной строки находятся в массиве подстановки, то:

#!/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']

Answer 2

Вы можете использовать следующий код двумя способами:

1. чтобы получить все строки в виде массива
2. чтобы вытащить строки по одной

Для использования (1), вызовите метод getStrings() (столько раз, сколько необходимо).

Для использования (2) вызывать метод next() only , пока 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()]);
    }

}

Answer 3

Гм, два цикла 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

[Обновление: исправлена ​​тупая опечатка.]

Answer 4

Вопрос был бы более понятен, если бы строка и массив не содержали и 'a'. Желаемый вывод не показывает никакой зависимости от входной строки.