Author Topic: A real problem  (Read 10047 times)

packman

  • Full Member
  • ***
  • Posts: 226
A real problem
« on: 六月 29, 2004, 02:53:36 pm »
I have a problem and ask for solutions here. I don't know how to do.

I need to print out a string of length "n",
1st position of the string is one of the following character: A,B,C
2nd position of the string is one of the following: L,M,N,
3rd position of the string is one of the following: W,X,Y,Z.
and so on...

I need to print out all the possible combinations, i.e.:
ALW
ALX
ALY
ALZ
AMW
....
....
CNY
CNZ

The possible characters at each position is a variable, so is the length of the string. The total possible combination should be 3*3*4*... in the above example.
Can anyone write a pseudo-code to accomplish this?
简单==完美

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
A real problem
« Reply #1 on: 六月 29, 2004, 08:48:22 pm »
There are several ways to solve this problem.

1. If your string are not very long and you have enough memory, then you can use a recursive function to put all the strings you want to print together. Start with the first string, attach every letter of the second string to every letter of the first string, pass the rest of the strings to the recursive function, attach every letter of the next string to every combination string you already made, and so on,....

2. If you want to print the combinations on the fly, use a vector to index into the position in each string, make up one combination, and update the index (just like number system), you stop until the index of the first string get out of range.

packman

  • Full Member
  • ***
  • Posts: 226
A real problem
« Reply #2 on: 六月 30, 2004, 08:42:28 am »
I had tried the first solution, seemed failed. It's just like traverse a tree (depth first). I ended up with this output (or something like that):
AMX
MX
X
.....

Your 2nd solution might work. I will give a try.
Thanks.
简单==完美

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
A real problem
« Reply #3 on: 六月 30, 2004, 10:30:39 am »
The first approach is the easiest, you must be doing something wrong. Recursive approach usually gives brief and elegant code, but it is also prone to mistakes.  If you know MATLAB, here's a MATLAB code that does the job using recursive approach (I just wrote it, took me 5~10 minutes :)

----------------------
function p=pcomp(a)
%generate all combinations of charactors in the strings of cell array A
p=gcomb(a{1}',a(2:end));
function p=gcomb(p,a)
if isempty(a)
  return;
else
  b = repmat(a{1},size(p,1),1);
  p = [repmat(p,length(a{1}),1) b(: )];
  p = gcomb(p,a(2:end));
end

-----------------------

If you don't know MATLAB, you will not understand the cell array stuff. But it can be easily done in C using a link list with pointers.

packman

  • Full Member
  • ***
  • Posts: 226
A real problem
« Reply #4 on: 六月 30, 2004, 10:35:02 am »
I don't know MATLAB. Can you explain it in C/C++?
简单==完美

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
A real problem
« Reply #5 on: 六月 30, 2004, 05:55:14 pm »
In C, you need to build a link list to connect all your strings. Then start with the first string, make all combinations with the next string, pass the next pointer, make all combinations to the existing one. You stop when the pointer points to null.

gravity

  • Newbie
  • *
  • Posts: 3
A real problem
« Reply #6 on: 八月 04, 2004, 04:30:37 pm »
// Given n, and n sets of characters, print out all possible strings of length n
// where the ith (i=0,1,...n-1) position in the string is from a character from set i
int func(int i, int n, char *str, char **tbl)
{
   if (i == n)
      return printf("%s\n", str);

   for (char *p = tbl; *p != '\0'; p++)
   {
      str = *p;
      func(i+1, n, str, tbl);
   }
}