2
$\begingroup$

I want an algorithm to list all possible ways to map a series of integers $M = \{1,2,3,...,m\}$ to another series of integers $N = \{1,2,3,...,n\}$ where $m > n$, subject to the constraint that only contiguous integers in $M$ map to the same integer in $N$.

E.g.: 5 -> 2:
(1, 2, 3, 4), (5)
(1), (2, 3, 4, 5)
(1, 2, 3), (4, 5)
(1, 2), (3, 4, 5)

This seems like it should be a standard problem with a well known solution, but I can't find it.

To clarify, I am not looking for the total number of solutions, but for pseudocode or the name of a corresponding algorithm to exhaustively list all solutions.

$\endgroup$
  • 2
    $\begingroup$ Welcome to CS.SE! What's the context where you encountered this? What have you tried so far? Have you tried some special cases (e.g., n=1, n=2, m=1, m=2) to get some intuition? This sounds like a pure math problem (combinatorics/counting). Is there some reason why it needs to be answered from a CS perspective? While we don't have an absolute policy against pure math questions here, they need to explain in the question why it needs to be answered from a CS perspective. Would you like to edit the question? $\endgroup$ – D.W. Sep 7 '16 at 18:13
  • $\begingroup$ I was looking for pseudocode or the name of a corresponding algorithm. Updated the question accordingly. $\endgroup$ – Paul Brodersen Sep 7 '16 at 18:43
  • $\begingroup$ Requests for code are offtopic here. $\endgroup$ – Raphael Sep 8 '16 at 7:18
1
$\begingroup$

Suppose that the image of your mapping has size $k$. This implies a division of $\{1,\ldots,M\}$ into $k$ contiguous intervals. By identifying each such interval with its largest point, we see that there are $\binom{M-1}{k-1}$ such partitions (since $M$ is always one of the $k$ largest points). For the actual colors chosen, the number of choices is $N(N-1)\cdots(N-k+1) = N!/(N-k)!$. The total number of mappings is thus $$ \sum_{k=1}^N \frac{N!}{(N-k)!} \binom{M-1}{k-1}. $$ Using this argument, it is not too hard to construct an algorithm to list all such mappings; the algorithm completely mirrors the argument.

$\endgroup$
  • $\begingroup$ The OP wants to enumerate the solutions, not count them. $\endgroup$ – Raphael Sep 8 '16 at 7:18
  • $\begingroup$ @Raphael Yes, that's a simple exercise given my argument. $\endgroup$ – Yuval Filmus Sep 8 '16 at 14:08
0
$\begingroup$

Enumerating all of them is quite easy:

The first number goes into the first bin.

For all other numbers: If you used n numbers, put the next number into the last bin (because you can't start another bin). If the number of remaining numbers equals the number of empty bins, put the next number into the next empty bin (because you wanted to use n bins; you need to use the next bin or you will have unused bins). Otherwise, enumerate both choices, where you put the next number into the last used bin or the first unused bin.

The execution time would be proportional to the size of the output

$\endgroup$
-2
$\begingroup$

Attempted a solution in python (start corresponds to the first element in $M$, stop-1 corresponds to the last element in $M$, and nbins corresponds to $|N|$):

import itertools
def find_bins(start, stop, nbins):
    if (nbins > 1):
        return list(list(itertools.product([range(start, ii)], find_bins(ii, stop, nbins-1))) for ii in range(start+1, stop-nbins+2))
    else:
        return [range(start, stop)]

It gives a human readable answer, but the output needs some cleanup.

$\endgroup$
  • 3
    $\begingroup$ Welcome to the site! We're looking for answers that explain what's going on, not just code dumps. In particular, you answer is meaningless to anyone who isn't a Python programmer: list(list(itertools.product(...))) doesn't mean anything to most people. $\endgroup$ – David Richerby Sep 7 '16 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.