Interview Question
Country: India
#include <iostream>
#include <string>
#include <queue>
#define N 4
using namespace std;
void FindCombination( char* s )
{
queue<string> strQ;
for ( int i = 0; i < N; i++ )
{
char ctemp = s[i];
if ( !strQ.empty() )
{
string strTemp = strQ.front();
strQ.pop();
int len = strTemp.length();
while ( len == i )
{
for ( int j = 0; j < len; j++ )
{
string strTemp2 = strTemp;
strQ.push( strTemp2.insert( j, 1, ctemp ) );
}
strQ.push( strTemp.append( 1, ctemp ) );
strTemp = strQ.front();
strQ.pop();
len = strTemp.length();
}
strQ.push( strTemp );
}
else
{
strQ.push( string( 1, ctemp ) );
}
}
while ( !strQ.empty() )
{
cout << strQ.front() << endl;
strQ.pop();
}
}
void main()
{
char s[] = { 'a', 'b', 'c', 'd' };
FindCombination( s );
}
How about permutation generation... Will operate as O(n!) complexity with O(n) memory:
public static void printPerms(String str){
if(str == null){
throw new NullPointerException();
}
if(str.length() == 0){
throw new IllegalArgumentException();
}
long max = fact(str.length());
PermBuilder p = new PermBuilder(str.toCharArray());
for(long i = 0; i < max; i++){
System.out.println(p.build(i));
}
}
private static long fact(long val){
long res = val;
while(val > 1){
val--;
res *= val;
}
return res;
}
static class PermBuilder{
private char[] arr;
public PermBuilder(char[] arr){
this.arr = arr;
}
public String build(long val){
char[] res = new char[this.arr.length];
System.arraycopy(this.arr, 0, res, 0, res.length);
for(int index = 0; index < res.length -1; index++){
int denom = res.length - index;
int swapIndex = index + val / denom;
char c = res[swapIndex];
char t = res[index];
res[index] = c;
res[swapIndex] = t;
val /= denom;
}
return new String(res);
}
}
#include<stdio.h>
main()
{
char array[4] = {'a','b','c','d'};
int i,j,k,l;
for(i=0;i<4;i++)
{
for(j=0;j<4;j++)
{
for(k=0;k<4;k++)
{
for(l=0;l<4;l++)
{
if(i!=j && j != k && k!= l && j != l && i!= k && i != l)
{
printf("%c%c%c%c\n",array[i],array[j],array[k],array[l]);
}
}
}
}
}
}
~
~
private char[] nextPermutation(char []a){
int n = a.length;
if (n == 1) return new char[]{};
int k = n - 2;
while(a[k] >= a[k+1]){
--k;
if (k < 0) return new char[]{};
}
int idx = -1;
for(int i = k + 1; i < n; ++i){
if (a[k] < a[i] && (idx == -1 || a[idx] > a[i])){
idx = i;
}
}
char tmp = a[idx];
a[idx] = a[k];
a[k] = tmp;
Arrays.sort(a, k + 1, n);
return a;
}
main body:
char []a = new char[]{'a', 'c', 'b', 'd'};
Arrays.sort(a)
while(a.length > 0){
System.out.println(Arrays.toString(a));
a = nextPermutation(a);
}
Works good for 4 symbols, but doesn't work for 5 :(
class Program
{
static char[] word = new char[] {'a','b','c','d'};
static char[] temp = new char[word.Length];
static List<string> result = new List<string>();
static void Main(string[] args)
{
for (int i = 0; i < word.Length; i++ )
{
word.CopyTo(temp, 0);
Combine();
Shift();
}
int counter = 0;
foreach(string s in (from c in result select c).Distinct())
{
Console.WriteLine((++counter).ToString() +" "+s);
}
Console.ReadLine();
}
static void Combine()
{
int end;
do
{
for (int start = 0; start < temp.Length - 1; start++)
{
end = start + 1;
do
{
result.Add(new string(word));
Swap(start, end++);
} while (end != temp.Length);
}
} while (new string(word) != new string(temp));
}
static void Swap(int first, int second)
{
char temp = word[first];
word[first] = word[second];
word[second] = temp;
}
static void Shift()
{
char temp = word[word.Length - 1];
for (int i = word.Length-1; i > 0; i--)
{
word[i] = word[i - 1];
}
word[0] = temp;
}
}
it works any string like abcd or abcdef
package com.rk.core.java;
/**
* A program that prints all combinations of a n letter word without using
* recursion technique.
*
* @author rkoda
*
*/
public class ABCDCombinations {
private void logic(String str) {
char charArr[] = new char[str.length()];
// convert into array
for (int i = 0; i < charArr.length; i++) {
charArr[i] = str.charAt(i);
}
// find total combinations
int tc = 1;
for (int i = 1; i <= charArr.length; i++) {
tc = tc * i;
}
System.out.println("total combinations : " + tc);
System.out.println(str);
int j = 0;
for (int i = 0; i < tc - 1; i++) {
char x = charArr[j+1];
charArr[j + 1] = charArr[j];
charArr[j] = x;
j++;
if (j + 1 == charArr.length) {
j = 0;
}
for (int k = 0; k < charArr.length; k++) {
System.out.print(charArr[k]);
}
System.out.println();
}
}
public static void main(String[] args) {
new ABCDCombinations().logic("abcd");
}
}
Iterative DFS using a stack
- aa January 07, 2015