Python: Every possible discrete function on two lists

Question

Imagine you have two lists.

list1 = ['a', 'b', 'c']
list2 = ['x', 'y']

what is the function that gives you back every possible function from the domain of list1 to the codomain of list2? The answer in this case would be

[ [('a', 'x'), ('b', 'y')],
  [('a', 'x'), ('c', 'y')],
  [('b', 'x'), ('a', 'y')],
  [('b', 'x'), ('c', 'y')],
  [('c', 'x'), ('a', 'y')],
  [('c', 'x'), ('b', 'y')] ]

This is a more general case of this question and answer which is the answer to this question when list1 and list2 are the same size.

Assume you don't know which is bigger, and either list could be 0, 1, or many elements. Preferably this should be expressible as some combination of itertools functions.

--EDITS--

The best I have so far is:

def everyPossibleAssignment(A, B):

if len(A) < len(B): return [list(zip(A, P)) for P in permutations(B, len(A))]
else: print "A must be smaller in size than B"

but I'm sure there's better.

If `list1` is the domain, shouldn't your functions be characterized by three pairs (a -> ?, b -> ?, c -> ?) rather than two? — senshin, Nov 23 '15 at 21:12
[`product` from itertools](https://docs.python.org/2/library/itertools.html#itertools.product) — R Nar, Nov 23 '15 at 21:13
Tomasz: thanks for catching that! I confused myself there. Product from itertools does not solve this actually. try it! — Alex Lenail, Nov 23 '15 at 21:23
No, what you have is exactly the right idea. The question is also the same as the much more popular https://stackoverflow.com/questions/12935194 but actually I think this version is much better asked. (Also, the problem should still be well defined when the lists are of equal length.) — Karl Knechtel, Mar 02 '23 at 02:39

senshin · Answer 1 · 2015-11-26T22:45:47.633

(OP has clarified in the comments that he doesn't actually want functions, but rather partial bijections between the two sets. This answer hence does not do what OP wants. I leave it here anyway in case it is of interest to future readers.)

You'll probably want to take the product of the domain with |domain| copies of the codomain:

from itertools import product

list1 = ['a', 'b', 'c']
list2 = ['x', 'y']

# The `zip` is just bookkeeping to transform (('a', 'b', 'c'), ('x', 'y', 'y'))
# into (('a', 'x'), ('b', 'y'), ('c', 'y'))
functions = [
    zip(*x) for x
    in product([list1], product(list2, repeat=len(list1)))
    ]

for function in functions:
    print(list(function))

Output:

[('a', 'x'), ('b', 'x'), ('c', 'x')]
[('a', 'x'), ('b', 'x'), ('c', 'y')]
[('a', 'x'), ('b', 'y'), ('c', 'x')]
[('a', 'x'), ('b', 'y'), ('c', 'y')]
[('a', 'y'), ('b', 'x'), ('c', 'x')]
[('a', 'y'), ('b', 'x'), ('c', 'y')]
[('a', 'y'), ('b', 'y'), ('c', 'x')]
[('a', 'y'), ('b', 'y'), ('c', 'y')]

This correctly produces 0 functions when the codomain is empty but the domain isn't, and 1 function (the empty function) when the domain is empty. (I'm assuming you only want total functions. If you want partial functions, then take products over combinations of the domain of length 0, 1, ..., |domain| instead of over just the domain.)

score 1 · Answer 2 · answered Nov 23 '15 at 21:26

1

The answer from the other question works just fine if you move some things around:

In [15]: list(list(zip(p, r)) for (r, p) in zip(repeat(list2), permutations(list1)))
Out[15]:
[[('a', 'x'), ('b', 'y')],
 [('a', 'x'), ('c', 'y')],
 [('b', 'x'), ('a', 'y')],
 [('b', 'x'), ('c', 'y')],
 [('c', 'x'), ('a', 'y')],
 [('c', 'x'), ('b', 'y')]]

answered Nov 23 '15 at 21:26

Randy

14,349
2
36
42

If this is what you want, OP, that's fine, but you should be aware that this is not actually "every possible [total] function from the domain of list1 to the codomain of list2". There should be `|list2|^|list1|` such functions, which is 8 in this case, not 6. – senshin Nov 23 '15 at 21:34
I think I didn't quite word my question right. I don't *quite* want a function, do I? Because I don't want any two parts of the domain to map to the same member of the codomain. Basically what I want is, if you take both lists, every one-to-one map between those two lists. – Alex Lenail Nov 24 '15 at 16:30
@AlexLenail In that case, what you actually want are "partial bijections" between the two lists. There should be `min(|domain|, |codomain|)!` many of those. I think this answer works correctly for generating partial bijections, but for a domain or codomain of 4 elements or more, it produces duplicate entries which you'll need to filter out. – senshin Nov 26 '15 at 22:45

Python: Every possible discrete function on two lists

2 Answers2