CareerCup

Iterative DFS using a stack

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

If we do not take letter repetition into account, then a permutation method will almost do all the work. If we can use a library function, the C++ next_permutation function is good enough.

#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");

	}
}