Creating strings from a template by replacing placeholders by all permutations of an input set

Question

I want to make a simple generator of strings.

User inputs a "template" for string. Template can have placeholders in any place in it. Then he inputs possible characters that can fit into any placeholder in string. How it should work:

INPUT:

a.b.
123

OUTPUT:

[
"a1b1", "a1b2", "a1b3",
"a2b1", "a2b2", "a2b3",
"a3b1", "a3b2", "a3b3"
]

I found some of my old python code, but i don't understand it at all.

I split the input string to array of strings and array of dots. Then I tried to increment just dots and each time just concat those two arrays in the right way. But I found a new trouble.

string[] splitted = kt_NonCur.Split('.');   // array of constant strings
char[] nch = new char[splitted.Length - 1]; // array of new chars (generated)
char lgc = goodLetters.Last( );    // last good char
for( int i = 0; i < nch.Length - 1; i++ ) // set up all nch to first letter
    nch[i] = goodLetters[0];
while( nch.Last( ) != lgc ) {  // until last nch is set to last good char
    outputData.Add($"{concatsplit(splitted, nch)}"); // concatsplit(s,n) concatenates two arrays into string
    nch[0] = up(nch[0]); // up(char) gets next character from goodLetters. If there is no next, it returns first letter.
    if( nch[0] == goodLetters[0] ) {
        nch[1] = up(nch[1]);    
        if(nch[1] == goodLetters[0]){
                nch[2] = up(nch[2]);
//                          .
//                              .
//                                  .
        }
    }
}

And the problem is: I am facing a dilemma. Either find better way, or limit number of placeholders so that the code ladder is not too long. Of course I would add then some code that checks if it is the last and stop executing code for others, but I still would have to make

The key word to search for is "permutations". There's not a feature for this built into .Net, but you should be able to find a library to help generate them. — Joel Coehoorn, Jun 12 '20 at 19:24
Adding to @JoelCoehoorn comment, the exact term here would be a "permutation with repetitions" (as the same repacement character can occur multiple times in the output. — Klaus Gütter, Jun 13 '20 at 06:47

Klaus Gütter · Accepted Answer · 2020-06-13T12:15:28.633

You can look at your problem this way: if you have P placeholders in your input string and the number of replacement characters is R, to construct every possibe output string you need at each step P numbers [0...R-1] (which can then serve as index into the replacement character list). Well, this is the definition of an integer with P digits in base R.

So let's write a helper class representing such integers:

class NDigitNumber
{
    int[] _digits;
    int _base;

    // construct an integer with the specified numer of digits in the specified base
    public NDigitNumber(int digits, int @base)
    {
        _digits = new int[digits];
        _base = @base;
    }

    // get the digit at the specified position
    public int this[int index] => _digits[index];

    // increment the number, returns false on overflow
    public bool Increment()
    {
        for (var pos = 0; pos < _digits.Length; pos++)
        {
            if (++_digits[pos] < _base)
                break;
            if (pos == _digits.Length-1)
                return false;
            for (var i = 0; i <= pos; i++)
                _digits[i] = 0;
        }
        return true;
    }
}

The Increment methods works like these mechanical counter devices where each digit wheel, when rotated from its maximum digit to the next, resets itself and all lower wheels to 0 and increments the next higher wheel.

Then we only have to iterate over all possible such integers to get the desired output:

var input = "a.b.";
var placeholder = '.';
var replacements = new[] { '1', '2', '3' };

// determine positions of placeholder in string
var placeholderPositions = new List<int>();
for (var i = 0; i < input.Length; i++)
{
    if (input[i] == placeholder)
        placeholderPositions.Add(i);
}

// iterate over all possible integers with
// placeholderPositions.Count digits
// in base replacements.Length
var number = new NDigitNumber(placeholderPositions.Count, replacements.Length);
do
{
    var result = new StringBuilder(input);
    for (var i = 0; i < placeholderPositions.Count; i++)
        result[placeholderPositions[i]] = replacements[number[i]];
    Console.WriteLine(result.ToString());
} while(number.Increment());

Output:

a1b1
a2b1
a3b1
a1b2
a2b2
a3b2
a1b3
a2b3
a3b3

score 1 · Answer 2 · answered Sep 21 '20 at 18:27

Based on accepted answer of this post:

public static IEnumerable<string> Combinations(string template, string str, char placeholder)
{
    int firstPlaceHolder = template.IndexOf(placeholder);   
    if (firstPlaceHolder == -1)     
        return new string[] { template };

    string prefix = template.Substring(0, firstPlaceHolder);    
    string suffix = template.Substring(firstPlaceHolder + 1);   
       
    var recursiveCombinations = Combinations(suffix, str, placeholder);

    return
        from chr in str
        from recSuffix in recursiveCombinations
        select prefix + chr + recSuffix;
 }

Usage:

List<string> combinations = Combinations("a.b.", "123", '.').ToList();

Creating strings from a template by replacing placeholders by all permutations of an input set

2 Answers2