How to find the permutation k in a given length?

Question

How to find permutations of k in a given length?

For instance:

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

---

This is not a homework problem. You can use any language, but more preferred: C / C ++ or C #. I know how to create recursion for LENGTH size, but not for custom size.

Answer 1

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

ba bn ab aa an nb na nn

The basic idea is to correct the first character, then form all permutations of length k-1, and then add the character to these permutations of length k-1. To deal with duplicate characters, we track the counter on the left (i.e. the one that can be used for permutations).

Not sample code, but should give you this idea. (If you find errors, 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 complete program that I use:

 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 2

What is wrong with the recursive solution, an additional parameter (depth) is passed, so that the recursive function immediately returns to 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

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

Answer 5

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

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

I don’t have enough money to explain the math behind it, but as I understand it, this is the least difficult way to iterate over all possible nCr options (i.e. 3C2 for your cat) in the collection.

Answer 6

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

Second computation of permutations of each subset using the next_permutation STL algorithm

I did not implement it, but I think it should work.