My combinatorics-fu is severely weak, it seems. There are of course
functions, where S(
m,
n) are the Stirling numbers of the second kind (number of ways to partition
m elements into
n non-empty subsets).
Let's reset.
Since you are only interested in the
N initial or final solutions, you can start with the set that contains |B|
|A| functions -- all solutions, plus those that do not map all elements in |B|.
Order this set of proposed solutions 0 .. |B|
|A|-1. This basically matches your outer loop. Not all iterations produce a result, so you'll most likely want to use a separate variable to hold the number of solutions provided.
Next, interpret the loop variable as a number in base |B|. That gives you |A| digits in base |B|. That is, if the loop variable is
i, |A|=m, |B|=n, then the first proposed pair is (A[0], B[
i mod n]), second is (A[1], B[(
i / n) mod n]), and so on; in general
(A[j], B[(i / nj) mod n]).
A practical example, if A and B are specified as arrays of strings:
Code:
unsigned long print_solutions(FILE *const out,
const char *const A[], const unsigned long m,
const char *const B[], const unsigned long n)
{
unsigned long solutions = 0UL;
unsigned long proposed = 0UL;
unsigned long bref[m];
unsigned char used[n];
unsigned long curr, k;
while (1) {
/* Current proposed solution. */
curr = proposed++;
/* Clear the used element map. */
memset(used, 0, sizeof used);
/* Convert 'curr' to a radix n number. */
for (k = 0; k < m; k++) {
const unsigned long digit = curr % n;
/* Mark digit used. */
used[digit] |= 1;
/* Add index of digit to proposed solution. */
bref[k] = digit;
/* Next digit. */
curr /= n;
}
/* If curr is nonzero, it was >= number of proposed solutions. */
if (curr)
break;
/* Verify all elements in B were used. */
for (k = 0; k < n; k++)
if (!used[k])
break;
/* If not, this is not a true solution. */
if (k < n)
continue;
/* This is a true solution. Print. */
solutions++;
printf("%lu. f([%s,%s]", solutions, A[0], B[bref[0]]);
for (k = 1; k < m; k++)
printf(", [%s,%s]", A[k], B[bref[k]]);
printf(")\n");
}
return solutions;
}
Instead of printing all the solutions, you could print just a desired number of first and/or last solutions. (The
if (curr) is only true if
curr was
>= m[sup]n , so you can also start at
m[sup]n-1 and count downwards toward zero, if you want the final solutions instead.)
Unless I'm too drunk,
Code:
int main(void)
{
static const char *const A[] = { "1", "2", "3", "4", "5" };
static const char *const B[] = { "a", "b", "c" };
unsigned long n;
n = print_solutions(stdout, A, sizeof A / sizeof A[0], B, sizeof B / sizeof B[0]);
printf("%lu solutions total.\n", n);
return 0;
}
does produce the expected 150 solutions, from f([1,c],[2,b],[3,a],[4,a],[5,a]) to f([1,a],[2,b],[3,c],[4,c],[5,c]).
This approach is still the same I originally described, except that you order a larger set that contains all the solutions, and some non-solutions too. Use a single integer to describe each unique solution -- that is what ordering means, after all. Usually you'll want to separate the integer to digits like above. Verify the solution is valid. Output the solution, and move to the next one.
