permutations with repeats algorithm with recursion

Question

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:

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.

I have edited your title. Please see, "Should questions include “tags” in their titles?", where the consensus is "no, they should not". — John Saunders
– John Saunders, Commented Oct 9, 2012 at 16:14
Please check out links from en.wikipedia.org/wiki/Permutations. There are also large amount of printed and online information on permutations, so it may be good idea to search existing body of knowledge. — Alexei Levenkov
– Alexei Levenkov, Commented Oct 9, 2012 at 16:21

ispiro · Accepted Answer · 2012-10-09 16:37:26Z

6

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);

edited Oct 9, 2012 at 16:37

answered Oct 9, 2012 at 16:29

ispiro

28k41 gold badges168 silver badges332 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

fubo Over a year ago

what is that textBox1.Text?

ispiro Over a year ago

@fubo It's the text in a Winforms textbox. You can use any other way to show the results. Like Console.Writeline for example.

Servy · Accepted Answer · 2012-10-09 16:32:57Z

5

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.

edited Oct 9, 2012 at 16:32

answered Oct 9, 2012 at 16:27

Servy

204k27 gold badges347 silver badges470 bronze badges

2 Comments

Joel Etherton Over a year ago

This sample does not account for repeated permutations. Each counted number will be unique.

Servy Over a year ago

@JoelEtherton No...the result of, for example, 8 printed as a string in base two is 111, which repeats 1 three times. This is relying on the fact that taking a number of different values (here options is the number of choices) n times (where n here is digits) results in options ^ digits possibilities; this lists out each of those possibilities.

shiggity · Accepted Answer · 2017-07-28 18:12:22Z

0

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;
    }
}

answered Jul 28, 2017 at 18:12

shiggity

5614 silver badges14 bronze badges

Comments

Dan W · Accepted Answer · 2023-12-31 17:44:58Z

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:

Collectives™ on Stack Overflow

permutations with repeats algorithm with recursion

4 Answers 4

2 Comments

2 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related