CODEWITHSUNDEEP
c#permutation
QuQu
QuQu

Reputation: 73

How to set the length of permutations of a given string?

I have the code which prints all possible permutations of a given string. How to set the length of one permutation? For example if the lenght is 2 then output should contains 6 possible permutations from ABCD.

class GFG 
{ 
    /** 
    * permutation function 
    * @param str string to 
    calculate permutation for 
    * @param l starting index 
    * @param r end index 
    */
    private static void permute(String str, 
                                int l, int r) 
    { 
        if (l == r) 
            Console.WriteLine(str); 
        else
        { 
            for (int i = l; i <= r; i++) 
            { 
                str = swap(str, l, i); 
                permute(str, l + 1, r); 
                str = swap(str, l, i); 
            } 
        } 
    } 

    /** 
    * Swap Characters at position 
    * @param a string value 
    * @param i position 1 
    * @param j position 2 
    * @return swapped string 
    */
    public static String swap(String a, 
                            int i, int j) 
    { 
        char temp; 
        char[] charArray = a.ToCharArray(); 
        temp = charArray[i] ; 
        charArray[i] = charArray[j]; 
        charArray[j] = temp; 
        string s = new string(charArray); 
        return s; 
    } 

// Driver Code 
public static void Main() 
{ 
    String str = "ABCD"; 
    int n = str.Length; 
    permute(str, 0, n-1); 
} 
}

Upvotes: 0

Views: 159

Answers (1)

Martin
Martin

Reputation: 16433

I originally missed that this was using a variable number of number arrangements (i.e. 5 source characters to all of the 2 character strings that could be generated). I've since revised this to show extra detail.

This is probably a mathematic rather than programming questions.

In order to calculate the number of permutations for source characters c with the maximum output length l, use the following:

result = c! / (c - l)!

In the case of your example of 4 characters and a maximum of 2-character output, this gives:

result = 4! / (4 - 2)!
       = 4! / 2!
       = 24 / 2
       = 12

To calculate this in C# is not difficult - calculate the factorial (!) of c and the difference between c and l and divide the first by the second:

Using the handy function below:

/// <summary>
/// Gets the factorial of the specified number.
/// </summary>
/// <param name="n">An int indicating the number to get the factorial of.</param>
/// <returns>An int indicating the factorial.</returns>
private static int getFactorial(int n)
{
    int returnValue = 1;

    while (n > 1)
        returnValue *= n--;

    return returnValue;
}

This can be done using:

int result = getFactorial(4) / getFactorial(4 - 2);
Console.WriteLine(result);

Output:

12

This can also be placed into its own function:

/// <summary>
/// Gets the factorial of n to length l.
/// </summary>
/// <param name="n">An int indicating the number of items in the set.</param>
/// <param name="l">An int indicating the length of the output.</param>
/// <returns>An int indicating the result.</returns>
private static int getFactorial(int n, int l)
{
    if (l > n) throw new ArgumentException("The legnth of the output may not be larger than the number of items", nameof(l));
    return getFactorial(n) / getFactorial(n - l);
}

Used as such:

Console.WriteLine($"The factorial of 4 by 2 is {getFactorial(4, 2)}");
Console.WriteLine($"The factorial of 5 by 3 is {getFactorial(5, 3)}");
Console.WriteLine($"The factorial of 6 by 2 is {getFactorial(6, 2)}");

Outputs:

The factorial of 4 by 2 is 12
The factorial of 5 by 3 is 60
The factorial of 6 by 2 is 30

Note: Using an int may not be the best choice. At low numbers it works well but as soon as you have a 13-character string (13!) it will overflow and give an invalid result. 13! = 6,227,020,800 which is clearly bigger than an int32 in C#.

Upvotes: 1

Related Questions