How can I find the permutations of k in a given length?
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.
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;
}
}
}
What's wrong with the recursive solution and passing an extra parameter (depth) so that the recursive function returns immediately for depth > n.
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;
}
}
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;
}
}
}
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.
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.
