Get permutation of specific characters in strings

Question

Given a string like "N00MNM" I need all permutations of zero '0' char inside the string maintaining all other chars in fixed order.

The result must be:

"N0M0NM" "N0MN0M" "N0MNM0" "NM00NM" "NM0N0M" "NM0NM0" "NMN0M0" "NMNM00" "0N0MNM" "0NM0NM" "0NMN0M" "0NMNM0"

Standard permutation function takes too time to do that work (we are talking of about 1500ms) and strings to test are longer than the sample one.

There's an algorithm for this?

How many `0` are allowed? The total given in the initial string? — dcg, Apr 05 '17 at 07:44
[Try this](http://stackoverflow.com/questions/13891200/how-to-get-all-the-possible-3-letter-permutations) — M. Adeel Khalid, Apr 05 '17 at 07:46
If your code takes 1.5 seconds to do 12 combinations.. you need to look at what your code does — BugFinder, Apr 05 '17 at 07:56

score 0 · Accepted Answer · answered Apr 05 '17 at 09:07

What you're trying to do can be done by getting all different positions in which the character 0 (in this case) can be placed and then including the total of 0 characters (00 in this case) in all positions of the string. These positions are taken from the string without all occurrences of 0. The code bellow does it:

public static IEnumerable<string> Combs(string str, char c)
{
    int count = str.Count(_c => _c == c);
    string _str = new string(str.Where(_c => _c != c).ToArray());

    // Compute all combinations with different positions
    foreach (var positions in GetPositionsSets(0, _str.Length, count))
    {
        StringBuilder _b = new StringBuilder();
        int index = 0;
        foreach (var _char in _str)
        {
            if (positions.Contains(index))
            { _b.Append($"{c}{_char}"); }
            else
            { _b.Append(_char); }
            index++;
        }
        if (positions.Contains(index))
            _b.Append(c);
        yield return _b.ToString();
    }
    //Compute the remaining combinations. I.e., those whose at some position
    //have the amount of supplied characters.
    string p = new string(c, count);
    for (int i = 0; i < _str.Length; i++)
    {
        yield return _str.Insert(i, p);
    }
    yield return _str + p;
}

//Gets all posible positions sets that can be obtain from minPos 
//until maxPos with positionsCount positions, that is, C(n,k) 
//where n = maxPos - minPos + 1 and k = positionsCount
private static IEnumerable<HashSet<int>> GetPositionsSets(int minPos, int maxPos, int positionsCount)
{
    if (positionsCount == 0)
        yield return new HashSet<int>();

    for (int i = minPos; i <= maxPos; i++)
    {
        foreach (var positions in GetPositionsSets(i + 1, maxPos,     positionsCount - 1))
        {    
            positions.Add(i);
            yield return positions;
        }
    }
}

The output of the code above for "N00MNM" is:

0N0MNM
0NM0NM
0NMN0M
0NMNM0
N0M0NM
N0MN0M
N0MNM0
NM0N0M
NM0NM0
NMN0M0
00NMNM
N00MNM
NM00NM
NMN00M
NMNM00

Get permutation of specific characters in strings

1 Answers1