Function that generates strings according to input

Question

I need a C# function that takes 2 strings as an input and return an array of all possible combinations of strings.

private string[] FunctionName(string string1, string string2) 
{
    //code
}

The strings input will be in the following format:

string1: basement

string2: a*fa

Now what I need is all combinations of possible strings using the characters in String2 (ignoring the * symbols), and keeping them in the same character position like this:

baaement, baaefent, baaefena, basefent, basemena, etc.

EDIT: This is not homework. I need this function for a piece of a program I am doing. The following is the code I have so far but it has some bugs.

static List<string> combinations = new List<string>();

static void Main(string[] args)
{
    //include trimming of input string
    string FoundRes = "incoming";
    string AltRes = "*2*45*78";
    List<int> loc = new List<int>();
    string word = "";


    for (int i = 0; i < AltRes.Length; i++)
    {
        if (AltRes[i] != '*')
        {
            loc.Add(i);
            word += AltRes[i];
        }
    }

    generate(word);
    string[] aaa = InsertSymbol(FoundRes, loc.ToArray(), AltRes, combinations);

    Console.WriteLine("input string: " + FoundRes);
    Console.WriteLine("Substitute string: " + AltRes);

    Console.WriteLine("============Output============");


    for (int j = 0; j < aaa.Length; j++)
    {

        Console.WriteLine(aaa[j]);
    }
    Console.ReadKey();
}//

private static void generate(string word)
{
    // Add this word to combination results set
    if (!combinations.Contains(word))
        combinations.Add(word);

    // If the word has only one character, break the recursion
    if (word.Length == 1)
    {
        if (!combinations.Contains(word))
            combinations.Add(word);
        return;
    }

    // Go through every position of the word
    for (int i = 0; i < word.Length; i++)
    {
        // Remove the character at the current position
        // call this method with the String
        generate(word.Substring(0, i) + word.Substring(i + 1));
    }
}//

private static string[] InsertSymbol(string orig, int[] loc, string alternative, List<string> Chars)
{
    List<string> CombinationsList = new List<string>();
    string temp = "";
    for (int i = 0; i < Chars.Count; i++)
    {
        temp = orig;
        for (int j = 0; j < Chars[i].Length; j++)
        {
            string token = Chars[i];

            if (alternative.IndexOf(token[j]) == loc[j])
            {
                temp = temp.Remove(loc[j], 1);
                temp = temp.Insert(loc[j], token[j].ToString());

                //     int pos = sourceSubst.IndexOf(token[j]);
                //     sourceSubst = sourceSubst.Remove(pos, 1);
                //     sourceSubst = sourceSubst.Insert(pos, ".");
            }
            else
            {
                temp = temp.Remove(alternative.IndexOf(token[j]), 1);
                temp = temp.Insert(alternative.IndexOf(token[j]), token[j].ToString());
            }
        }
        CombinationsList.Add(temp);
    }
    return CombinationsList.ToArray();
}//

Tell us what you've tried so far, and what you're having trouble with. We don't mind helping with homework but we aren't going to do it all for you. — Aaronaught
– Aaronaught, Commented Mar 20, 2010 at 19:14
-this is not homework (i done my part but now i am stuck ... see edit part of original post) -hacking passwords??? i have more interesting things to do with my life :) — mouthpiec
– mouthpiec, Commented Mar 20, 2010 at 21:59

Anthony Pegram · Accepted Answer · 2010-03-20 22:00:17Z

It does sound like homework. As a suggestion, I would ignore the first parameter and focus on getting all possible permutations of the second string. What's turned off, what's turned on, etc. From that list, you can easily come up with a method of swapping out characters of the first string.

On that note, I'm in the uncomfortable position of having a function ready to go but not wanting to post it because of the homework implication. I'd sure love for somebody to review it, though! And technically, there's two functions involved because I just happened to already have a generic function to generate subsets lying around.

Edit: OP says it isn't homework, so here is what I came up with. It has been refactored a bit since the claim of two functions, and I'm more than open to criticism.

using System;
using System.Collections.Generic;
using System.Text;

class Program
{
    static void Main()
    {
        string original = "phenomenal";
        string pattern = "*xo**q*t**";

        string[] replacements = StringUtility.GetReplacementStrings(original, pattern, true);

        foreach (string replacement in replacements)
            Console.WriteLine(replacement);

        Console.Read();
    }

    public static class StringUtility
    {
        public static string[] GetReplacementStrings(string original, string pattern, bool includeOriginal)
        {
            // pattern and original might not be same length
            int maxIndex = Math.Max(original.Length, pattern.Length);

            List<int> positions = GetPatternPositions(pattern, maxIndex, '*');
            List<int[]> subsets = ArrayUtility.CreateSubsets(positions.ToArray());
            List<string> replacements = GenerateReplacements(original, pattern, subsets);

            if (includeOriginal)
                replacements.Insert(0, original);

            return replacements.ToArray();
        }

        private static List<string> GenerateReplacements(string original, string pattern, List<int[]> subsets)
        {
            List<string> replacements = new List<string>();
            char[] temp = new char[original.Length];

            foreach (int[] subset in subsets)
            {
                original.CopyTo(0, temp, 0, original.Length);
                foreach (int index in subset)
                {
                    temp[index] = pattern[index];
                }

                replacements.Add(new string(temp));
            }

            return replacements;
        }

        private static List<int> GetPatternPositions(string pattern, int maxIndex, char excludeCharacter)
        {
            List<int> positions = new List<int>();

            for (int i = 0; i < maxIndex; i++)
            {
                if (pattern[i] != excludeCharacter)
                    positions.Add(i);
            }

            return positions;
        }
    }

    public static class ArrayUtility
    {
        public static List<T[]> CreateSubsets<T>(T[] originalArray)
        {
            List<T[]> subsets = new List<T[]>();

            for (int i = 0; i < originalArray.Length; i++)
            {
                int subsetCount = subsets.Count;
                subsets.Add(new T[] { originalArray[i] });

                for (int j = 0; j < subsetCount; j++)
                {
                    T[] newSubset = new T[subsets[j].Length + 1];
                    subsets[j].CopyTo(newSubset, 0);
                    newSubset[newSubset.Length - 1] = originalArray[i];
                    subsets.Add(newSubset);
                }
            }

            return subsets;
        }
    }
}

hi .... thanks for the post :) this is not homework. Please check the Edit part of my original post I have so far, but i am not happy with it since it has some bugs! do you have an other solution?
fantastic this is what I wanted! :) I will take a look at the code to check where I made a mistake in my code!

Rune FS · Accepted Answer · 2010-03-20 20:06:08Z

0

since it's hopw work I'd only suggest some way to solve the problem rather than writing the code.

if you loop the second parameter every time you hit a letter you'll have to options either use the letter from the first argument or the letter from the second. collect all these optins together with the index. keep a list of the parts from the first argument that will never change. iterate thorugh those two lists to created all the possible permutations

answered Mar 20, 2010 at 20:06

Rune FS

21.7k7 gold badges65 silver badges101 bronze badges

Comments

Pratik Deoghare · Accepted Answer · 2010-03-20 20:54:19Z

Decimal to Binary converted code is ~~stolon~~ copied from here.

static void Main()
{
    string string1 = "basement";
    string string2 = "**a*f**a";

    string[] result = GetCombinations(string1, string2);

    foreach (var item in result)
    {
        Console.WriteLine(item);
    }        

}

private static string[] GetCombinations(string string1, string string2)
{
    var list = new List<List<char>> { new List<char>(), new List<char>() };

    var cl = new List<char>();

    List<string> result = new List<string>();

    for (int i = 0; i < string1.Length; i++)
    {
        if (string2[i] == '*')
        {
            cl.Add(string1[i]);
        }
        else
        {
            list[0].Add(string1[i]);
            list[1].Add(string2[i]);
        }
    }

    int l = list[0].Count;

    for (int i = 0; i < (Int64)Math.Pow(2.0,l); i++)
    {
        string s = ToBinary(i, l);
        string ss = "";

        int x = 0;
        int y = 0;

        for (int I = 0; I < string1.Length; I++)
        {

            if (string2[I] == '*')
            {
                ss += cl[x].ToString();
                x++;
            }
            else
            {
                ss += (list[int.Parse(s[y].ToString())][y]);
                y++;
            }
        }
        result.Add(ss);
    }
    return result.ToArray<string>();
}

public static string ToBinary(Int64 Decimal, int width)
{
    Int64 BinaryHolder;
    char[] BinaryArray;
    string BinaryResult = "";

    while (Decimal > 0)
    {
        BinaryHolder = Decimal % 2;
        BinaryResult += BinaryHolder;
        Decimal = Decimal / 2;
    }

    BinaryArray = BinaryResult.ToCharArray();
    Array.Reverse(BinaryArray);
    BinaryResult = new string(BinaryArray);

    var d = width - BinaryResult.Length;

    if (d != 0) for (int i = 0; i < d; i++) BinaryResult = "0" + BinaryResult;

    return BinaryResult;
}

user287107 · Accepted Answer · 2010-03-20 19:16:33Z

-1

which password cracker do you want to program? :) how about

if string2 contains '*'

    foreach(char ch in string1)
        replace first * with ch, 
        execute FunctionName 
else  
   print string2

answered Mar 20, 2010 at 19:16

user287107

9,4371 gold badge34 silver badges47 bronze badges

Collectives™ on Stack Overflow

Function that generates strings according to input

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related