1

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

Improve this question

4 Answers 4

Reset to default
2

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']
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Wow. I like generators as much as anyone, but this looks like an example from "Math Made Difficult".
Without generators it is just: print map(''.join,product('abcd',repeat=len('ba')))
0

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.

Improve this answer

Comments

0

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

Improve this answer

3 Comments

Did you mean res.append(i + j)? And it is wrong. The result strings always end with a character from b.
Yes, thanks, corrected. And the result string does always end with a character from b.
The correct result array for the given input should contain strings such as 'bc', 'cc', 'bd', 'dd',.. Your code never produces them.
0

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

}
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.