Thread: Problem on repeated permutation

  1. #1
    Registered User
    Join Date
    May 2012
    Posts
    13

    Problem on repeated permutation

    I was trying to write a program that makes repeated
    permutations of two given variables(a,b) in userdefined number
    n(1<n<1000) of places.
    for example
    1)if user inputs 3,
    then the output must be
    aaa
    aab
    aba
    abb
    baa
    bab
    bba
    bbb
    2)if user inputs 4
    then the output must be
    aaaa
    aaab
    aaba
    aabb
    abaa
    abab
    abba
    abbb
    baaa
    baab
    baba
    babb
    bbaa
    bbab
    bbba
    bbbb


    My program works if only I know in advance how many places are there.
    But my problem is to give a generic code that gives out output in any number of n.
    Code:
    #include<stdio.h>
    #include<conio.h>
    int main(void)
    {
    int n;
    char set[]="ab";
    int i,j,k,l;
    char str[5];
    printf("How many places?\n");
    scanf("%d",&n);
    n=4;         //as this code will handle only 4 as input,needs improvement
    for(i=0;i<2;i++)
    {
    for(j=0;j<2;j++)
    {
    for(k=0;k<2;k++)  /*4 loops to handle 4 places,needs improvement*/
    {
    for(l=0;l<2;l++)
    {
    str[0]=set[i];
    str[1]=set[j];
    str[2]=set[k];
    str[3]=set[l];
    str[4]='\0';
    printf("%s\n",str);
    }}}}
    return 0;
    }

  2. #2
    Registered User
    Join Date
    Dec 2011
    Posts
    795
    There's a much better way to calculate permutations (which isn't exactly what you're doing, but w.e) than using a system of nested for loops.

    You'll first need to set up a few variables:
    Code:
    	int size_set = 2;
    	char *chrset = "ab";
    
            int set_len = 4;
    	char res[set_len + 1];
    	char *tmp = res;
    	
    
    	int n, pos, permc, perm_per_len, wordlen;
    Then, calculate how many permutations you'll actually need:
    Code:
    	perm_per_len = 1;
    	for (n = 0; n < set_len; n++) 
    		perm_per_len *= size_set;
    Finally, generate the actual permutations:
    Code:
    	for (n = 0; n < perm_per_len; n++) {
    		permc = 1;
    		tmp = res;
    		for (wordlen = 0; wordlen < set_len; wordlen++) {
    			pos = (n / permc) % size_set;
    			*tmp++ = chrset[pos];
    			permc *= size_set;
    		}
    		printf("%s\n", res);
    	}
    Don't go and copy my code, but use it as an example.

  3. #3
    Registered User
    Join Date
    May 2012
    Posts
    13
    Thanks for your reply..
    why in your program you have taken the size of the array as
    Code:
    char [res+1]
    it is not legal .i changed it to anything greater than expected.
    Anyways.i got the flaw in my logic.....where i was using loops to evaluate position ,you used a mathematical expression to do the same.
    and so now it is generic and working.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Permutation problem
    By alpine in forum C Programming
    Replies: 1
    Last Post: 02-25-2011, 10:45 PM
  2. Permutation Problem?
    By chottachatri in forum C++ Programming
    Replies: 8
    Last Post: 06-10-2008, 09:32 PM
  3. Problem creating a recursive string permutation function
    By indigo0086 in forum C++ Programming
    Replies: 4
    Last Post: 10-10-2006, 10:09 AM
  4. string permutation problem
    By Korg in forum C Programming
    Replies: 3
    Last Post: 10-07-2005, 08:19 AM
  5. permutation problem, need help!!!
    By Eric in forum C++ Programming
    Replies: 0
    Last Post: 10-01-2001, 12:29 PM