Microsoft Interview Question
Software Engineer / DevelopersCountry: United States
your algo is correct BUT instead of printing the *suffix* of length n of the permuted string you should print the *prefix* of it. Then for n = 2 you get precisely:
ab ac ad ba bc bd ca cb cd da db dc
This is a very simple recursive function. Below is the explanation of the recurrence, followed by the code:
1. Say your string is "abcd"
2. At each step of the recursion, you can either pick a character and move to the next character. So in the first step of the recursion, you can pick "a" and call the recursive function again.
3. OR you can skip "a" and call the recursive function again
Code in C#:
// Call recursive function
PrintCombinations("abcd", 3, "", 0);
public static void PrintCombinations(string targetString, int targetLength, string comboSoFar, int pos)
{
if (comboSoFar.Length == targetLength)
{
Console.WriteLine(comboSoFar);
return;
}
if(pos>=targetString.Length) return;
char c=targetString[pos];
PrintCombinations(targetString, targetLength, comboSoFar + c, pos + 1);
PrintCombinations(targetString, targetLength, comboSoFar, pos + 1);
}
Adding some comment to make the recursion easier to follow with the explanation:
public static void PrintCombinations(string targetString, int targetLength, string comboSoFar, int pos)
{
if (comboSoFar.Length == targetLength) // This is the desired length of the combination
{
Console.WriteLine(comboSoFar);
return;
}
if(pos>=targetString.Length) return;
char c=targetString[pos];
PrintCombinations(targetString, targetLength, comboSoFar + c, pos + 1); // Case: Pick current character and move to next
PrintCombinations(targetString, targetLength, comboSoFar, pos + 1); // Case: Skip current character and move to next
}
Below is the C# code both with and without Recursion:
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Enter the input string: ");
string input = Console.ReadLine();
Console.WriteLine("Enter length for combinations: ");
int length;
if (!Int32.TryParse(Console.ReadLine(), out length))
{
Console.WriteLine("Enter valid Integer input. Try Again!!");
}
else
{
if (length > input.Length)
{
Console.WriteLine("The length for combinations should be lesser than the length of the input string.");
}
else
{
//PrintCombinations(input, length);
PrintCombinationsRecursive(input+input.Substring(0, length-1), length, 0);
Console.ReadKey();
}
}
}
/// <summary>
///
/// </summary>
/// <param name="input"></param>
/// <param name="length"></param>
private static void PrintCombinations(string input, int length)
{
for (int i = 0; i < input.Length; ++i)
{
int k = 0;
for (int j = 0; j < length; ++j)
{
if (i + j < input.Length)
{
Console.Write(input[i + j]);
}
else
{
Console.Write(input[k]);
++k;
}
}
Console.WriteLine();
}
}
/// <summary>
///
/// </summary>
/// <param name="input"></param>
/// <param name="length"></param>
private static void PrintCombinationsRecursive(string input, int length, int i)
{
if (input.Length-i < length)
{
return;
}
string combin = input.Substring(i, length);
Console.WriteLine(combin);
PrintCombinationsRecursive(input,length,++i);
}
}
Hi
I have lot of difficulty understanding this recursion. Can someone pl spare sometime to explain how to formulate the recursion behind this problem ?
That is, pls do ot explain some approach that works. I want to understand the mechanics behind this so that I can apply this to any combinatorial problem that is similar.
Thanks
python:
#!/usr/bin/python
def recurse(a,b):
if (len(b) == 3):
print ''.join(b)
else:
for i in range(len(a)):
c = b[:]
d = a[:]
c.append(d.pop(i))
recurse(d,c)
if __name__ == "__main__":
a="abcd"
b=[]
recurse(list(a),b)
abc
abd
acb
acd
adb
adc
bac
bad
bca
bcd
bda
bdc
cab
cad
cba
cbd
cda
cdb
dab
dac
dba
dbc
dca
dcb
public class Permute1
{
StringBuilder out = new StringBuilder();
public void permute (String input, int start, int length)
{
if (out.length() == length)
{
System.out.println(out);
return;
}
for (int i = start ; i < input.length() ; i++)
{
out.append(input.charAt(i));
permute (input, i + 1 , length);
out.setLength(out.length() - 1);
}
}
public static void main(String[] args) {
Permute1 p = new Permute1();
p.permute("abcd", 0, 2);
}
}
Java solution
Below is the solution in Java
- loveCoding January 10, 2012