On Jul 14, 8:53 am, ankit mahendru <[email protected]> wrote:
> Write the code to print combinations of a given array (n& r were given) e.g
> for abcde .r=3 ...print " abc", "bcd' "cde" etc
The problem has a nice recursive structure. To choose r items from a
set of items numbered m..n, make a decision to choose one of these.
Say it's i, where m <= i <= n. Then recur to find the rest of the
(r-1) items from the subset i+1...n. The base case is r==0, which
means you have found all the items you need and can print the result.
(You can refine this a bit to get rid of some useless recursive calls.
How?)
Here is one approach of many possible to code this idea:
#include <stdio.h>
#include <string.h>
typedef struct choice_s {
struct choice_s *prev;
int i;
} CHOICE;
void print_choices(char *set, CHOICE *choices)
{
if (choices) {
print_choices(set, choices->prev);
putchar(set[choices->i]);
}
}
void print_combinations(char *set, int n, int r, CHOICE *choices)
{
if (r == 0) {
print_choices(set, choices);
putchar('\n');
}
else {
CHOICE choice[1] = {{ choices }};
for (choice->i = choices ? choices->i + 1 : 0; choice->i < n;
choice->i++)
print_combinations(set, n, r - 1, choice);
}
}
int main(int argc, char *argv[])
{
int r;
char *s;
if (argc == 3 && sscanf(argv[2], "%d", &r) == 1 && strlen(argv[1])
>= r)
s = argv[1];
else {
s = "abcde";
r = 3;
}
print_combinations(s, strlen(s), r, 0);
return 0;
}
$ ./a.out
abc
abd
abe
acd
ace
ade
bcd
bce
bde
$
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
