How to find permutation of k in a given length?

Question

How can I find the permutations of for example 2 in a size of 3.

For example:

The word cat has 3 letters: How can I find all the permutations of 2 in the word cat. Result should be: ac, at, ca, ac, etc...

---

This is not a homework problem. Any language could be used but more preferable: C/C++ or C#. I know how to create the recursion for size LENGTH but not for a custom size.

Answer 1

since its not homework, i can assume you don't mind using some libraries others created? If your search the web, you can find many. one of which is this. give it a try.

Answer 2

What's wrong with the recursive solution and passing an extra parameter (depth) so that the recursive function returns immediately for depth > n.

Answer 3

Not the most efficient, but it works:

public class permutation
{
    public static List<string> getPermutations(int n, string word)
    {
        List<string> tmpPermutation = new List<string>();
        if (string.IsNullOrEmpty(word) || n <= 0)
        {
            tmpPermutation.Add("");
        }
        else
        {
            for (int i = 0; i < word.Length; i++)
            {
                string tmpWord = word.Remove(i, 1);
                foreach (var item in getPermutations(n - 1, tmpWord))
                {
                    tmpPermutation.Add(word[i] + item);
                }
            }
        }
        return tmpPermutation;
    }
}

Answer 4

Here is one in C#, which should work even with repeated characters. For example on "banana" for permutations of length 2 it gives:

ba bn ab aa an nb na nn

The basic idea is to fix the first character, then form all permutations of length k-1, then prepend the character to those k-1 length permutations. To deal with duplicate characters, we keep track of the count left (i.e the ones which can be used for sub-permutations).

Not exemplary code, but should give you the idea. (If you find bugs, let me know and I can edit).

static List<string> Permutations(Dictionary<char, int> input, int length) {
    List<string> permutations = new List<string>();

    List<char> chars = new List<char>(input.Keys);

    // Base case.
    if (length == 0) {
        permutations.Add(string.Empty);
        return permutations;
    }

    foreach (char c in chars) {

        // There are instances of this character left to use.
        if (input[c] > 0) {

            // Use one instance up.
            input[c]--;

            // Find sub-permutations of length length -1.
            List<string> subpermutations = Permutations(input, length - 1);

            // Give back the instance.
            input[c]++;

            foreach (string s in subpermutations) {

                // Prepend the character to be the first character.
                permutations.Add(s.Insert(0,new string(c,1)));

            }
        }
    }

    return permutations;
}

And here is the full program I have, to use it:

using System;
using System.Collections.Generic;

namespace StackOverflow {

    class Program {
        static void Main(string[] args) {
            List<string> p = Permutations("abracadabra", 3);
            foreach (string s in p) {
                Console.WriteLine(s);
            }
        }

        static List<string> Permutations(string s, int length) {
            Dictionary<char, int> input = new Dictionary<char, int>();
            foreach (char c in s) {
                if (input.ContainsKey(c)) {
                    input[c]++;
                } else {
                    input[c] = 1;
                }
            }
            return Permutations(input, length);
        }

        static List<string> Permutations(Dictionary<char, int> input, 
                                                          int length) {
            List<string> permutations = new List<string>();

            List<char> chars = new List<char>(input.Keys);
            if (length == 0) {
                permutations.Add(string.Empty);
                return permutations;
            }

            foreach (char c in chars) {
                if (input[c] > 0) {
                    input[c]--;
                    List<string> subpermutations = Permutations(input, 
                                                                length - 1);
                    input[c]++;

                    foreach (string s in subpermutations) {
                        permutations.Add(s.Insert(0,new string(c,1)));
                    }
                }
            }

            return permutations;
        }
    }
}

Answer 5

If I'm not mistaken, this problem can be solved by combinadics too, as on http://en.wikipedia.org/wiki/Combinadic/, there are reference implementations there too.

I have used the Java solution (http://docs.google.com/Doc?id=ddd8c4hm_5fkdr3b/) myself for generating all possible triples from a sequence of numbers, this should be no different.

I lack the wherewithal to explain the math behind it, but as I understand this is the least complex way to iterate over all possible nCr (i.e. 3C2 for your cat example) choices within a collection.

Answer 6

First find the possible subsets of your array. You can do this in a recursive way it was discussed in Iterating over subsets of any size

Second calculate the permutations of every subset with the STL-Algorithm next_permutation

I haven't implemented it but i think it should work.

Answer 7

void Prem (char *str, int k, int length) { if (k == length-1){ printf("%s\n",str); return; } else { for (int i = k ; i < length; ++i) { char t = str[k]; str[k] = str[i]; str[i] = t; Prem(str,k+1,length); t = str[k]; str[k] = str[i]; str[i] = t; } } }