Replace string characters from array.

Question

I have a string (of undertermined length) that I want to copy a lot of times replacing one character at a time from an array (of undertermined length) of characters.

So say I have this string: 'aa'
And this array: ['a', 'b', 'c', 'd']

after some magic for-looping stuff there would be an array like: ['aa', 'ab', 'ac', 'ad', 'ba', 'bb' ... 'dc', 'dd']

How would you do this? I tried something using three for loops but I just can't seem to get it.

Edit
The dependency on the string is the following:

Say the string is: 'ba'
then the output should be: ['ba', 'bb', 'bc', 'bd', 'ca' ... 'dd']

Answer 1

The question would be clearer if the string and the array would not both contain an 'a'. The desired output does not show any dependency on the input string.

Answer 2

Um, two for loops should do it: 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

[Update: dumb typo corrected.]

Answer 3

If an order of strings in the result array doesn't matter and all chars from the initial string are in the substitution array then:

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

---

Here's a solution for a general case. Replacements are performed in a lexicographic order:

#!/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 4

You can use the following code in two ways:

1. to get all strings as an array
2. to pull strings one at a time

For usage (1), call the getStrings() method (as many times as desired).

For usage (2), call the next() method only as long as hasNext() returns true. (Implementing a reset() method is left as an exercise for the reader! ;-)

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()]);
    }

}