1
$\begingroup$

This imaginary problem involves a vector of length 5, with each value to be selected from a unique range of values.

A real-world example might include 5 different single-digit combination locks.

How many different ways could I lock a single gate, assuming that I can use any number of locks?

Assuming that each lock takes values ([1-3], [1-3], [1-3], [1-3], [1-3]) There would be 3^5 == 243 possible combinations. But I'm also interested in calculating the total number of combinations possible by using subsets of the 5 locks, so adding the solution for each combination of four locks, each combination of 3 locks and so on. The solution would also ideally be generalisable so that each list of values can differ i.e. ([1-2], [1-10], [A-C] ... )

Does there exist a mathematical solution to this problem?


edit:

In the main, the question is about a general purpose mathematical solution. For example, to find the number of combination of a set of length (3), one uses 3! ie. 6 combinations of [1,2,3].

I was wondering if there exists a general purpose solution to the above scenario. If not, I would think it could be possible to program something to recurse over the possibilities, which I guess is why I decided to post it here first as my search for a mathematical solution came up empty handed.


Some examples of inputs and outputs as requested:

input = [A,B,C] [1,2,3,4,5] [G,H]

output combinations are all possible combinations of those three lists, without needing to sample all three lists. Note combinations, hence [A1G] == [G1A]

i.e. (this is not all the combinations): A B C A1 A2 A3 ... C4 C5 A1G A1H A2G A2H ... C5G C5H ... 1 2 3 4 5 1G 1H . . 5G 5H .. G H

$\endgroup$
  • 3
    $\begingroup$ I'm not sure I understand what you're asking. But, since you ask for a mathematical solution and this is the computer science section of Stack Exchange, I think your question is off-topic. $\endgroup$ – David Richerby Jun 26 '17 at 8:59
  • 1
    $\begingroup$ I have no idea what you're asking. Can you give a few sample input/output pairs? $\endgroup$ – Yuval Filmus Jun 26 '17 at 12:15
  • 1
    $\begingroup$ @DavidRicherby Do you think the question is clear enough to be migrated to Mathematics? Yuval doesn't seem to think so. $\endgroup$ – Raphael Jun 26 '17 at 16:03
  • $\begingroup$ @Raphael I've no strong opinion about whether we should migrate. Math.se is a big site so one more question probably wouldn't make much difference to them. Ideally, the asker will clarify and we can make a decision then. $\endgroup$ – David Richerby Jun 26 '17 at 17:33
  • 1
    $\begingroup$ I'm not sure this comment thread is well-suited for extended discussion about whether this question is on-topic; it might be better to take this to Computer Science Meta by posting a question there. For background, I'll link to our existing policy on which kinds of math questions are considered on-topic here. (Cc: @fade2black) JohnL_10, do you feel this question is best answered by computer scientists? If so, it might help to explain why in the question. Regardless, please do edit the question to clarify what you are asking. $\endgroup$ – D.W. Jun 26 '17 at 18:53
1
$\begingroup$

(Your lock values are all distinct. We could instead consider the locks distinct.)

We add a nil value to each lock, representing the lock not being included. Using your example, we get ...

input = [A,B,C,nil] [1,2,3,4,5,nil] [G,H,nil]

... to choose from. There are ...

$$4 \times 6 \times 3 = 72 $$

... ways to do this.

In general, from sets $Locks$, there are ...(

$$\prod_{l \in Locks} (\vert l \vert + 1)$$

... ways.


So far, so mathematical. Now let's generate the possibilities. I'll have to use a programming language. My choice is Clojure, a Lisp. We should be able to at least verify the above result.

(def locks '[[A,B,C] [1,2,3,4,5] [G,H]])

(defn combos [ls]
  (if (empty? ls)
    [()]
    (let [[l & ls] ls
          sub-list (combos ls)]
      (concat
        sub-list
        (for [x l, y sub-list] (cons x y))))))

Now

(count (combos locks))
=> 72

... as expected.

There are better ways to depict the problem space, but this'll surely do.

$\endgroup$
  • $\begingroup$ Using Nil values would solve this problem. Thank you for the answer! $\endgroup$ – JohnL_10 Jun 27 '17 at 11:21

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.