wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> combinations
        
(Message started by: manni_rox_14 on Feb 13th, 2009, 5:57am)
Title: combinations
Post by manni_rox_14 on Feb 13th, 2009, 5:57am
make a function(in c)..and pass to it 2 arguements(a string and no.)..then print all d combinations of d string of length=(length of string passed) - (d no. passed as arguement)..
for example
string passed="abcde";
no. passed=2;
all combinations are:
abc,abd,abe,acd,ace,ade,bcd,bce,bde,cde..
Title: Re: combinations
Post by nks on Feb 15th, 2009, 11:18pm
I think it requires to get following combinations  
                                   n
                                      C
                                        d   .
Title: Re: combinations
Post by SMQ on Feb 16th, 2009, 5:51am
One possible algorithm is given in this thread (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1209056303).  There's probably a better one in Knuth, volume 4, fascicle 3 (http://www-cs-faculty.stanford.edu/~uno/taocp.html) but I don't have my copy at hand at the moment.

--SMQ
Title: Re: combinations
Post by SMQ on Feb 17th, 2009, 10:55am
Here's a compact implementation of "Algorithm T" due to Knuth above:

void string_combinations(char * s, int d) {
 int n, j, x, *c;

 if (d <= 0) { puts(s); putchar('\n'); return; }
 if (d >= (n = strlen(s))) return;
 c = (int *)malloc((n + 2 - d)*sizeof(int));

 for(j = 0; j < n - d; ++j) c[j] = j;
 c[j + 1] = 0; x = n;

 do {
   c[j--] = x;

   for(x = 0; c[x] < n; ++x) { putchar(s[c[x]); } putchar('\n');

   if (j >= 0) { x = j + 1; continue; }
   for(x = c[j = 0] + 1; x == c[j + 1]; x = c[++j] + 1) c[j] = j;
 } while (j < n - d);

 free(c);
}

--SMQ
Title: Re: combinations
Post by Grimbal on Jul 15th, 2009, 5:10am
Here is a simple solution.  It is certainly slower than Knut's solution because of the recursivity and all the String operations involved.

package misc;

public class Substrings
{
    public void generate(String str, int remove){
        if( remove>=0 && remove<=str.length() ){
            sub("", str, str.length() - remove);
        }
    }
    
    public void sub(String prefix, String str, int len){
        if( len==0 ){
            System.out.println(prefix);
        } else
        if( len==str.length() ){
            System.out.println(prefix+str);
        } else {
            sub(prefix+str.substring(0,1), str.substring(1), len-1);
            sub(prefix, str.substring(1), len);
        }
    }

    public static void main(String[] args){
        Substrings s = new Substrings();
        s.generate("abcde", 2);
    }
}
Title: Re: combinations
Post by mistaken_id on Sep 2nd, 2009, 2:44pm
How do we handle repititions with Grimbal's algo..such that repeated combinations are not printed.....
Title: Re: combinations
Post by Dufus on Sep 19th, 2009, 12:57pm

on 09/02/09 at 14:44:17, mistaken_id wrote:
How do we handle repititions with Grimbal's algo..such that repeated combinations are not printed.....


May sound naive but how about ignoring repeated characters in the input character set
Title: Re: combinations
Post by towr on Sep 19th, 2009, 2:49pm

on 09/19/09 at 12:57:16, Dufus wrote:
May sound naive but how about ignoring repeated characters in the input character set
Then you won't get the required output. If you're asked for recombinations of "aab", then "ab" and "ba" are not among them, you want "aab", "aba" and "baa". You just don't want to get them twice for both arrangements of a's.
Title: Re: combinations
Post by Dufus on Sep 19th, 2009, 3:33pm

on 09/19/09 at 14:49:24, towr wrote:
Then you won't get the required output. If you're asked for recombinations of "aab", then "ab" and "ba" are not among them, you want "aab", "aba" and "baa". You just don't want to get them twice for both arrangements of a's.


Isnt combination an UNORDERED collection of distinct elements by definition.
Or am I missing something here.
Title: Re: combinations
Post by towr on Sep 20th, 2009, 1:24am

on 09/19/09 at 15:33:35, Dufus wrote:
Isnt combination an UNORDERED collection of distinct elements by definition.
Or am I missing something here.
Well, the example given certainly suggest order matters. In fact the whole problem would be pointless under that definition, because any input has just one combination, itself (in any order).
But perhaps "permutation" would have been the better word to use.
Title: Re: combinations
Post by mistaken_id on Sep 21st, 2009, 3:39pm
Can anyone explain the logic behind SMQ's code
Title: Re: combinations
Post by SMQ on Sep 22nd, 2009, 6:23am
Excerpting from Knuth (TAOCP, vol. 4, fasc. 3, ch. 7.2.1.3):
[Here n is the total number of elements, t is the number of elements to list, and c1, c2, ..., ct is the list of indexes of elements in a particular combination.]
 [We] can generate combinations lexicographically by [... finding] the rightmost element cj that can be increased and then [setting] subsequent elements cj-1...c1 to their smallest possible values:

Algorithm L (Lexicographic combinations).  This algorithm generates all t-combinations ct...c2c1 of the n numbers {0, 1, ..., n - 1}, given n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif t http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif 0.  Additional variables ct+1 and ct+2 are used as sentinals.
L1. [Initialize.] Set cj http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/leftarrow.gif j http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/leftarrow.gif 1 for 1 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif j http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif t; also set ct+1 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/leftarrow.gif n and ct+2 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/leftarrow.gif 0.
L2. [Visit.] Visit the combination ct...c2c1.
L3. [Find j.] Set j http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/leftarrow.gif 1. Then, while cj + 1 = cj+1, set cj http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/leftarrow.gif j - 1 and j http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/leftarrow.gif j + 1; repeat until cj + 1 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif cj+1.
L4. [Done?] Terminate the algorithm if j > t.
L5. [Increase cj.] Set cj http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/leftarrow.gif cj + 1 and return to L2. http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/blacksquare.gif

[...]

 But the [runtime of Algorithm L] can be embarrassingly large when t is near n and [the number of unused elements] is small.  Indeed, Algorithm L occastionally sets cj http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/leftarrow.gif j - 1 needlessly, at times when cj already equals j - 1.  Further scrutiny reveals that we need not always search for the index j that is needed in steps L4 and L5, since the correct value of j can often be predicted from the actions just taken.  For example, after we have increased c4 and reset c3c2c1 to their starting values 210, the next combination will inevitably increase c3.  These observations lead to a tuned-up version of the algorithm:

Algorithm T (Lexicographic combinations). This algorithm is like Algorithm L, but faster. It also assumes, for convenience, that t < n.
T1. [Initialize.] Set cj http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/leftarrow.gif j - 1 for 1 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif j http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif t; then set ct+1 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/leftarrow.gif n, ct+2 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/leftarrow.gif 0, and j http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/leftarrow.gif t.
T2. [Visit.] (At this point j is the smallest index such that cj+1 > j.) Visit the combination ct...c2c1. Then, if j > 0, set x http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/leftarrow.gif j and go to step T6.
T3. [Easy case?] if c1 + 1 < c2, set c1 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/leftarrow.gif c1 + 1 and return to T2.  Otherwise set j http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/leftarrow.gif 2.
T4. [Find j.] Set cj-1 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/leftarrow.gif j - 2 and x http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/leftarrow.gif cj + 1. If x = cj+1, set j http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/leftarrow.gif j + 1 and repeat this step until x http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif cj+1.
T5. [Done?] Terminate the algorithm if j > t.
T6. [Increase cj.] Set cj http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/leftarrow.gif x, j http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/leftarrow.gif j - 1, and return to T2. http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/blacksquare.gif

Now j = 0 in step T2 if and only if c1 > 0, so the assignments in step T4 are never redundant.
In my implementation, t is replaced by n - d since we're given the number of elements to exclude, array c is indexed from 0 to t - 1 rather than from 1 to t, steps T3 and T4 are combined into a single for loop, and step T6 is moved to the top of the main loop so as to form a more traditional do-while structure.  moving T6 before T2 also changes the initialization in T1 slightly.

Hope that helps!  Knuth's algorithms tend to take some studying to understand... ;)

--SMQ
Title: Re: combinations
Post by sonam on May 13th, 2011, 12:47am
Here's another approach:
If string size is less than 32(in a 32-bit machine), then the sequence of bits, having 'd' set bits can be produced and each sequence corresponds to a valid combination.

string length=6, d=3:

000111
001011
001101
001110
010011
010101
010110
011010
011100
:   :    :

How to write code to produce these hexagrams?
Title: Re: combinations
Post by wiley on Aug 17th, 2011, 12:16pm
How about this:
where len=output string length
n=length of string;
permute(arr,0) //Initial call

permute(char[] arr, int pos)
{
   if(pos == len)
   {
           printarray(arr, len);
           return;
   }
   permute(arr, pos+1);
   for(int i=pos+1;i<=n;i++)
   {
           if(swap(arr,pos,i)) // returns true if characters are different
           {
               permute(arr, pos+1);
               swap(arr,pos,i);
           }
   }
}


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board