A algorithm to enumerate all the combinations of given numbers
Author : Anders Ma [2011_0419]
*/
#include
int array[100];
int cursor = 0;
void enumerate(int n)
{
int i;
for(i = 0; i < cursor; ++i)
printf("%d,", array[i]);
if (cursor != 0)
printf("\n");
for (i = 0; i < n; ++i) {
array[cursor++] = i + 1;
enumerate(i);
cursor--;
}
}
int
main(int argc, char **argv)
{
enumerate(5);
return 0;
}
anders@ubuntu:~/c$ ./enum
1,
2,
2,1,
3,
3,1,
3,2,
3,2,1,
4,
4,1,
4,2,
4,2,1,
4,3,
4,3,1,
4,3,2,
4,3,2,1,
5,
5,1,
5,2,
5,2,1,
5,3,
5,3,1,
5,3,2,
5,3,2,1,
5,4,
5,4,1,
5,4,2,
5,4,2,1,
5,4,3,
5,4,3,1,
5,4,3,2,
5,4,3,2,1,
1 条评论:
Hey Anders, that's sweet code!
Yesterday we were talking about Python. I said that one of the strengths of Python is that its standard libraries usually do 90% of what you want, and the other 10% is usually easy.
In this case, there is a standard library called itertools. Here's the documentation:
http://docs.python.org/library/itertools.html
A quick note: Python has something called an "iterable". It's something that you can iterate ("迭代"?) along, to get each value. "for" loops can be given iterables. A list of values is an iterable, but not all iterables are lists of values. For example, you can have a special function called a "generator" that computes the next value in the series not all at once, but when it is needed.
itertools has a function called "permutations()". You give permutations() an iterable and a length, and it gives you an iterable which will give you all the possible permutations of the input.
For example, we could call "permutations('abcde', 2)" and you can iterate over the result to get all the permutations of length two from 'abcde'. The reason we can pass 'abcde' is because a string is also iterable: If you iterate over it, you get each letter.
What permutations() returns is an iterable. If you iterate over it, you will get every permutation. Note that even if the number of computations is bigger than the computer's memory, that's ok, because the iterable that permutations() returns is a generator function: It will compute the next item as you iterate over it.
Here's something else useful: the built-in string class has a method called "join()". It takes an iterable of strings, and joins them together with the string of the object you're calling join() on. For example:
print ":".join('abc', 'def', 'ghi')
will print:
abc:def:ghi
It's very useful for formatting output, such as putting in commas (',').
Here's another useful thing: List comprehensions. If I run this:
squares = (x * x for x in range(10))
Then squares is a list with this value:
(0, 1, 4, 9, 16, 25, 36, 49, 64, 81)
So, here's the program:
1: #! /usr/bin/env python
2:
3: import itertools
4:
5: for len in range(5):
6: perms = itertools.permutations('12345', len + 1)
7: print ", ".join(("".join(str(u) for u in t) for t in perms))
Line 3 says to pull in itertools.
Line 5 is a loop to go through each of the lengths, from 0 to 4 (we'll add one later).
Line 6 is the magic: perms becomes an iterable of all the permutations.
Line 7 is just some magic to print it to the screen with commas.
This is a good example of Python's libraries usually having something cool to solve your problem, and with the richness of Python's data structures, you can concentrate on the problem, and not worry about how to express it in C. Python is really fun!
发表评论