CODEWITHSUNDEEP
c#recursionpermutation
marseilles84
marseilles84

Reputation: 426

permutations with repeats algorithm with recursion

I'm having some trouble getting this to work using one function, instead of having to use many.

If I want to get permutations with repeats like 2^3. permutations with repeats

to get:

000
001
101
011
100
101
110
111

I can have this function: 

   static void Main(string[] args)
    {
        three_permutations(2);
        Console.ReadLine();
    }


    static void three_permutations(int y)
    {

        for (int aa = 0; aa < y; aa++)
        {
            for (int bb = 0; bb < y; bb++)
            {
                for (int cc = 0; cc < y; cc++)
                {
                    Console.Write((aa));
                    Console.Write((bb));
                    Console.Write((cc));
                    Console.WriteLine();
                }
            }
        }

    }

But then to do 4 (like 2^4), the only way I can think is this:

  static void four_permutations(int y)
    {
            for (int aa = 0; aa < y; aa++)
            {
                for (int bb = 0; bb < y; bb++)
                {
                    for (int cc = 0; cc < y; cc++)
                    {
                        for (int dd = 0; dd < y; dd++)
                        {
                            Console.Write((aa));
                            Console.Write((bb));
                            Console.Write((cc));
                            Console.Write((dd));
                            Console.WriteLine();
                        }
                    }
                }
            }
     }

but I'm sure there's a better way using recursion I'm just not sure how to do it. I appreciate any help. Thanks.

Upvotes: 2

Views: 3682

Answers (4)

Dan W
Dan W

Reputation: 3628

Here's another answer which doesn't rely on recursion or math operators such as Pow, and is about as simple as it can be:

    static IEnumerable<int[]> permute(int size)
    {
        int[] i = new int[size];
        while (true) {
            yield return i;
            int index = 0;
            while (index < size) {
                i[index]++;
                if (i[index] == size) {
                    i[index] = 0;
                    index++;
                }
                else break;
            }
            if (index == size) break;
        }
    }

    // Example usage:
    static void Main(string[] args)
    {
        foreach (int[] i in permute(3))
        {
            foreach (int j in i) Console.Write(j + " ");
            Console.WriteLine();
        }
    }

Output:

0 0 0
1 0 0
2 0 0
0 1 0
1 1 0
2 1 0
0 2 0
1 2 0
2 2 0
0 0 1
1 0 1
2 0 1
0 1 1
1 1 1
2 1 1
0 2 1
1 2 1
2 2 1
0 0 2
1 0 2
2 0 2
0 1 2
1 1 2
2 1 2
0 2 2
1 2 2
2 2 2

Upvotes: 0

shiggity
shiggity

Reputation: 561

Without recursion, and to a list for later use, in less than 10 lines.

public IEnumerable<List<int>> YieldCombinationsOfN(int places, int digitMin, int digitMax)
{            
    int n = digitMax - digitMin + 1;
    int numericMax = (int)Math.Pow(n, places);

    for (int i = 0; i < numericMax; i++)
    {
        List<int> li = new List<int>(places);
        for(int digit = 0; digit < places; digit++)
        {
            li.Add(((int)(i / Math.Pow(n, digit)) % n) + digitMin);
        }
        yield return li;
    }
}

Upvotes: 0

ispiro
ispiro

Reputation: 27633

void permutations(string text, int numberOfDigits, int numberOfChars)
{
    if (numberOfDigits > 0)
        for (int j = 0; j < numberOfChars; j++)
            permutations(text + j.ToString(), numberOfDigits - 1, numberOfChars);
    else textBox1.Text += text + "\r\n";
}

and call:

permutations("", 3, 2);

Upvotes: 6

Servy
Servy

Reputation: 203802

Permutations with repetition is essentially counting in another base.

public static void Permutations(int digits, int options)
{
    double maxNumberDouble = Math.Ceiling(Math.Pow(options, digits));
    int maxNumber = (int)maxNumberDouble;
    for (int i = 0; i < maxNumber; i++)
    {
        Console.WriteLine(Convert.ToString(i, options).PadLeft(3, '0'));
    }
}

The example that you've printed is essentially counting from 0 to 8 in base 2.

Upvotes: 5

Related Questions