Author |
Topic: combinations (Read 4811 times) |
|
manni_rox_14
Newbie
Posts: 1
|
 |
combinations
« on: Feb 13th, 2009, 5:57am » |
 Quote  Modify
|
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..
|
|
 IP Logged |
|
|
|
nks
Junior Member
Gender: 
Posts: 145
|
|
Re: combinations
« Reply #1 on: Feb 15th, 2009, 11:18pm » |
Quote Modify
|
I think it requires to get following combinations
n
C
d .
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: combinations
« Reply #2 on: Feb 16th, 2009, 5:51am » |
Quote Modify
|
One possible algorithm is given in this thread. There's probably a better one in Knuth, volume 4, fascicle 3 but I don't have my copy at hand at the moment.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: combinations
« Reply #3 on: Feb 17th, 2009, 10:55am » |
Quote Modify
|
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
|
|
IP Logged |
--SMQ
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: combinations
« Reply #4 on: Jul 15th, 2009, 5:10am » |
Quote Modify
|
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);
}
}
|
| « Last Edit: Jul 15th, 2009, 5:12am by Grimbal » |
IP Logged |
|
|
|
mistaken_id
Junior Member
Posts: 132
|
|
Re: combinations
« Reply #5 on: Sep 2nd, 2009, 2:44pm » |
Quote Modify
|
How do we handle repititions with Grimbal's algo..such that repeated combinations are not printed.....
|
| « Last Edit: Sep 2nd, 2009, 2:46pm by mistaken_id » |
IP Logged |
|
|
|
Dufus
Newbie
Posts: 43
|
|
Re: combinations
« Reply #6 on: Sep 19th, 2009, 12:57pm » |
Quote Modify
|
on Sep 2nd, 2009, 2:44pm, 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
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: combinations
« Reply #7 on: Sep 19th, 2009, 2:49pm » |
Quote Modify
|
on Sep 19th, 2009, 12:57pm, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Dufus
Newbie
Posts: 43
|
|
Re: combinations
« Reply #8 on: Sep 19th, 2009, 3:33pm » |
Quote Modify
|
on Sep 19th, 2009, 2:49pm, 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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: combinations
« Reply #9 on: Sep 20th, 2009, 1:24am » |
Quote Modify
|
on Sep 19th, 2009, 3:33pm, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
mistaken_id
Junior Member
Posts: 132
|
|
Re: combinations
« Reply #10 on: Sep 21st, 2009, 3:39pm » |
Quote Modify
|
Can anyone explain the logic behind SMQ's code
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: combinations
« Reply #11 on: Sep 22nd, 2009, 6:23am » |
Quote Modify
|
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  t 0. Additional variables ct+1 and ct+2 are used as sentinals.
L1. [Initialize.] Set cj  j 1 for 1  j t; also set ct+1 n and ct+2 0.
L2. [Visit.] Visit the combination ct...c2c1.
L3. [Find j.] Set j 1. Then, while cj + 1 = cj+1, set cj j - 1 and j j + 1; repeat until cj + 1  cj+1.
L4. [Done?] Terminate the algorithm if j > t.
L5. [Increase cj.] Set cj cj + 1 and return to L2. 
[...]
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 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 j - 1 for 1 j t; then set ct+1 n, ct+2 0, and j 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 j and go to step T6.
T3. [Easy case?] if c1 + 1 < c2, set c1 c1 + 1 and return to T2. Otherwise set j 2.
T4. [Find j.] Set cj-1 j - 2 and x cj + 1. If x = cj+1, set j j + 1 and repeat this step until x cj+1.
T5. [Done?] Terminate the algorithm if j > t.
T6. [Increase cj.] Set cj x, j j - 1, and return to T2.
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
|
|
IP Logged |
--SMQ
|
|
|
sonam
Newbie
Posts: 1
|
|
Re: combinations
« Reply #12 on: May 13th, 2011, 12:47am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
wiley
Newbie
Posts: 12
|
|
Re: combinations
« Reply #13 on: Aug 17th, 2011, 12:16pm » |
Quote Modify
|
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);
}
}
}
|
| « Last Edit: Aug 17th, 2011, 12:17pm by wiley » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print