How to generate a list of permutations for a given binary number

[madhu.garimilla]

if (4,2) is given as input we have to list all the 4 digit binary numbers containing two 1s ie, 1100,1010,1001.... etc. i need a java program to implement this. can anyone help???

[peter_budo]

Yes, you can help your self by first reading forum rules and then one of most important announcements

[PoovenM]

Yes, please tell us how you think the problem could be solved and we will help you program/tweak or provide an alternative to your solution. Here's a tip though, often algorithms exists that provide an efficient answer, but sometimes brute force is really all you need.

[jwenting]

now let's try that with input (10000000000, 325523) :)
I do want some performance out of it of course...

[iamthwee]

now let's try that with input (10000000000, 325523) :)
I do want some performance out of it of course...

I think that's gonna crash :D

[iamthwee]

Yes, please tell us how you think the problem could be solved and we will help you program/tweak or provide an alternative to your solution. Here's a tip though, often algorithms exists that provide an efficient answer, but sometimes brute force is really all you need.

What efficient algorithm?

[PoovenM]

Yes, well while efficiency might be real fun, sometimes it’s not worth the effort don’t you think? This student seems like a first year student so perhaps a brilliant solution isn’t really needed. I doubt that it would crash though, probably just take a real long time to respond ;) thought that would be implementation dependant hey!

This question seems like a Statistic problem where counting principals can be used. Consider the case with four digit numbers, if each digit could only be one of two options then there are 2 * 2 * 2 * 2 possible numbers that could be formed. I’ve done this kind of Statistics three years ago and I’m rather rusty, but an efficient algorithm would be based on the rules of statistics :)

[iamthwee]

Statistics, sounds like a combination problem to me.

[PoovenM]

To me permutations are part of Statistics hehe my bad! We did a section called counting principals were these concepts were discussed. Hey if someone knows how it works, would ja post it here please? I can’t for the life of me remember how it’s done! Perhaps from 4 choose 2: 4C2 = 6? Well I still think a brute force method is really all that is required. A method which we will not discuss since the student who posted this question hasn’t shown initiative to answer the question as yet.

[iamthwee]

>A method which we will not discuss since the student who posted this question hasn’t shown initiative to answer the question as yet.

It doesn't really matter since 95% of ppl here post once never to return. So why not have a discussion.

I was thinking about:-

CombinationGenerator

import java.math.BigInteger;
public class CombinationGenerator
{
 private int[] a;
 private int n;
 private int r;
 private BigInteger numLeft;
 private BigInteger total;
 public CombinationGenerator ( int n, int r )
 {
    if ( r > n )
    {
       throw new IllegalArgumentException ();
    }
    if ( n < 1 )
    {
       throw new IllegalArgumentException ();
    }
    this.n = n;
    this.r = r;
    a = new int[r];
    BigInteger nFact = getFactorial ( n );
    BigInteger rFact = getFactorial ( r );
    BigInteger nminusrFact = getFactorial ( n - r );
    total = nFact.divide ( rFact.multiply ( nminusrFact ) );
    reset ();
 }
 public void reset ()
 {
    for ( int i = 0; i < a.length; i++ )
    {
       a[i] = i;
    }
    numLeft = new BigInteger ( total.toString () );
 }
 public BigInteger getNumLeft ()
 {
    return numLeft;
 }
 public boolean hasMore ()
 {
    return numLeft.compareTo ( BigInteger.ZERO ) == 1;
 }
 public BigInteger getTotal ()
 {
    return total;
 }
 private static BigInteger getFactorial ( int n )
 {
    BigInteger fact = BigInteger.ONE;
    for ( int i = n; i > 1; i-- )
    {
       fact = fact.multiply ( new BigInteger ( Integer.toString ( i ) ) );
    }
    return fact;
 }
 public int[] getNext ()
 {
    if ( numLeft.equals ( total ) )
    {
       numLeft = numLeft.subtract ( BigInteger.ONE );
       return a;
    }
    int i = r - 1;
    while ( a[i] == n - r + i )
    {
       i--;
    }
    a[i] = a[i] + 1;
    for ( int j = i + 1; j < r; j++ )
    {
       a[j] = a[i] + j - i;
    }
    numLeft = numLeft.subtract ( BigInteger.ONE );
    return a;
 }
}

test

public class test
{ 
 public test()
 {
  //
 } 
 public static void main ( String[] args )
 {
    String[] elements = {"1", "2", "3", "4"};
    int[] indices;
    CombinationGenerator x = new CombinationGenerator ( elements.length, 2 );
    StringBuffer combination;
    while ( x.hasMore () )
    {
       combination = new StringBuffer ();
       indices = x.getNext ();
       for ( int i = 0; i < indices.length; i++ )
       {
          combination.append ( elements[indices[i]] );
       }
       System.out.println ( combination.toString () );
    }
 }
}

[PoovenM]

One second thought the 4C2 operation doesn't make sense! Ah the things my mind comes up with when it knows not what to do lol

Wow very nifty solution Iamthwee! For the most part it looks rather complex... and so I'm not really sure how the solution is found... but then I've never been one to enjoy understanding someone else's code without their guidance. Here's my brute force attempt:

import java.util.Scanner;

class Permutations
{
	public static void main(String[]args) throws Exception
	{
		System.out.print("Please enter the number of digits the number consists of: ");
		Scanner stdIn = new Scanner(System.in);
		int n = stdIn.nextInt();
		System.out.print("Please enter the number of 1's we are dealing with: ");
		int p = stdIn.nextInt();
		//should check for validity of input
		int count = 1;//the first number is formed below:
		char[] num = new char[n];
		for (int k = 0; k < n; k++)
			if (k < p)
				num[k] = '1';
				else num[k] = '0';
		System.out.println("The following permutations have been found:");
		System.out.println(num);
		for (int finalPerm = 0; finalPerm < p; finalPerm++)
		{
			for (int oneIndex = finalPerm; oneIndex < p; oneIndex++)
				for (int stringIndex = oneIndex; stringIndex < n; stringIndex++)
					if (num[stringIndex] == '0')
					{
						num[oneIndex] = '0';//new number
						num[stringIndex] = '1';
						count++;
						System.out.println(num);
						num[oneIndex] = '1';//revert to old number
						num[stringIndex] = '0';
					}
			num[finalPerm] = '0';//now set digit 1 to the end of the number and repermutate
			num[n - finalPerm - 1] = '1';
		}
		System.out.println("There are a total of " + count + " permutations.");
	}
}

Consider the formally mentioned question, my solution works as follows:

The number is first formed:
1100

Then the first '1' is moved to everywhere it could be placed:
0110
0101

Then the second '1' is moved to everywhere it could be placed:
1010
1001

Finally I consider placing the first '1' in the end of the number:
0011

Of course the 'final' step takes into consideration all cases.

I'm not really sure if this solution even works! But hey it's a learning process huh :D

Now a permutation consists of reordering to form distinct numbers... so 1100 and 1100 where the 1's have been swapped is not seen as distinct... I think! So anyway I ignored 1100 as a permutation to 1100. I hope that makes sense :)

[iamthwee]

When I get my java compiler up and running I will test it. Ha ha.

[iamthwee]

I don't have my compiler quite set up. But just perusing your code my hunch is that your algo is flawed. So yours won't work.

Some of the nCr (pronounced n choose r)calculations don't marry.

I was also thinking, you could potentially use a permutation algo but just suppress all duplicates to achieve a similar result, which might actually be more relevant to the actual question. yup.

(btw that code aint't mine it is nicked from elseweb but the ideas are explained clearly in Knuth's bible of Algorithms)

[madhu.garimilla]

sorry guys,, i was not been to this thread last week as i am busy.. thanks a lot for all ur replies... I am working for an MNC.. actuallty this question was asked in Oracle interview..i was given a binary number 1100 and asked me to write a program in java to generate all permutations of this number

[madhu.garimilla]

I know how to generate permutations for a given string , so iahave taken this binary number as a string and tried but this binary number conatins only 1s and 0s so some permutations we get are duplicate .. like we get 1010 and again 1010... totally we have to get C(4,2) different binary sequences.. but using String permutations technique i am getting 4! diff sequences.. can u help me how to remove those duplicates????

[PoovenM]

Permutation… sigh. Well I suppose the easiest approach would be to keep track of all the generated permutations in a vector (or perhaps hash table) and so when a new permutation is generated you simply compare it will the preexisting ones. Should it not be found then it is a valid permutation and so increment your counter. Of course this approach is really messy and slow!

I think it would help if you post your algorithm/code here and perhaps someone (not me cause this is really beyond me) could suggest improvements in your methodology so as to prevent duplications. I’ve never worked with permutations before, though it does seem fascinating hehe

[madhu.garimilla]

hey here i am giving my algo...

public class Main {

        static void permute(StringBuffer str, final int strt, final int len) {
int i = strt;
int j;

for ( i = strt; i < len-1; ++i ) {
for ( j = i+1; j < len; ++j ) {

swap(str,i,j);
permute(str, i+1, len);
swap(str,i,j);
}
}
System.out.println(str);
}

static void swap(StringBuffer str,int i,int j)
{
    char temp1,temp2;
    temp1 = str.charAt(i); 
temp2 = str.charAt(j);
str.deleteCharAt(i);
str.insert(i,temp2);
str.deleteCharAt(j);
str.insert(j,temp1);

}

public static void main(String args[]) {
StringBuffer str = new StringBuffer("abc");

permute(str, 0, str.length() );

String s=(String)new Main();


}


}

can anyone suggest me on how to remove the duplicate sequences from being displayed/generated ..

[iamthwee]

>can anyone suggest me on how to remove the duplicate sequences from being displayed/generated

http://www.roseindia.net/java/jdk6/CollectionTest.shtml

But that's got bad time complexity. You wanna be looking instead at

http://www.cosc.canterbury.ac.nz/tad.takaoka/isaac.pdf

and if my hunch is correct, because your problems consists of only 1's and 0's you can probably take a few more shortcuts and employ a few more tricks to simplify the solution.

[~s.o.s~]

> can anyone suggest me on how to remove the duplicate sequences from being displayed/generated
By using a better algorithm like 'Heap Permute'. See this. Though the solution is in C++, with almost no effort, you can port it to Java.

[iamthwee]

Erm how does heap permute remove duplicates or help when removing duplicates?

[no1zson]

Amazing. Do you guys just know this stuff, and sit down and logically work your way through it? or do you have manuals and texts from years of experience that you refer to in order to get the algorithms and apis and methods and things like that?

[~s.o.s~]

Ah, pardon me, I misread the question, my bad.

[iamthwee]

> Ah, pardon me, I misread the question, my bad.

Now there is an understatement.