How to write a function that uses a pair and returns sets of cardinality of 2 in Python?

Question

I need help writing some Python code that input is a list A that represents a set and whose output is a list of the subsets of A that have cardinality of 2. I want to do this using an import, my professor wants me to understand where the numbers come from.

For instance:

if A = [a, b, c], then
listPairs(A) = [[a, b], [a, c], [b, c]].

Possible duplicate of [How to get all possible combinations of a list’s elements?](https://stackoverflow.com/questions/464864/how-to-get-all-possible-combinations-of-a-list-s-elements) — Derte Trdelnik, Mar 09 '18 at 20:52
Your question should include your own efforts. https://stackoverflow.com/help/how-to-ask — Ash, Mar 09 '18 at 21:15

score 4 · Answer 1 · edited Mar 09 '18 at 21:26

4

Try itertools.combinations. The following returns all subsequences of length 2 of A.

import itertools
[set(x) for x in itertools.combinations(A, 2)]

Examples:

# AB AC AD BC BD CD
[set(x) for x in itertools.combinations('ABCD', 2)]
# 012 013 023 123
[set(x) for x in itertools.combinations(range(4), 3)]

This is the syntax for the functional equivalent:

list(map(set, itertools.combinations(A, 2)))

edited Mar 09 '18 at 21:26

jpp

159,742
34
281
339

answered Mar 09 '18 at 20:52

Garrett Gutierrez

747
3
16

Thanks, but I am not allowed to use imports :( is there any way you know of doing it without the import? – Ethan Walser Mar 09 '18 at 20:54
1

Just adding it here that `itertools.combinations` will return a generator object and that OP wants to make it a list. – Spade Mar 09 '18 at 20:54
1

Yes, @EthanWalser. There are algorithms for doing this. Do a bit of research, and I'm sure you'll find some good resources. – Christian Dean Mar 09 '18 at 20:55
2

@Spade Sure, and he also wants a list of sets, not a list of arbitrary iterables. But that's a trivial fix: `[set(combi) for combi in combinations(A, 2)]`. (For a novice, I'd probably write that with an explicit loop rather than a one-liner comprehension, but you get the idea.) – abarnert Mar 09 '18 at 20:56
1

@EthanWalser That is definitely something you are going to want to edit into the question! – Garrett Gutierrez Mar 09 '18 at 20:56
@EthanWalser Look at the [`itertools` docs](https://docs.python.org/3/library/itertools.html). Notice that `combinations` doesn't just explain how it works, it includes "roughly equivalent" (simplified) code to do the same thing. Obviously, don't just copy and paste that code and claim it as your own, or your teacher will easily figure it out and fail you—and. more importantly, you won't learn anything. But read that code and try to understand what it's doing, and then you'll be able to write this easily. – abarnert Mar 09 '18 at 20:59
1

@EthanWalser Or, rather, you'll be able to get started, and to ask questions about the specific parts that stumped you. – abarnert Mar 09 '18 at 21:00
Thanks @abarnet ! I appreciate it man! I am trying to grasp both python and discrete structures at the same time and its hard for me to see the connection sometimes! – Ethan Walser Mar 09 '18 at 21:00
1

@EthanWalser In general, a lot of the Python stdlib serves not just as a handy library, but useful source code. For many modules, there's a link to the source at the top of the docs, and that source is worth reading. `itertools` is actually not one of those modules, but its docs are chock full of sample code from simplified implementations of some of the functions to recipes for tying them together. – abarnert Mar 09 '18 at 21:15

score 0 · Answer 2 · answered Mar 09 '18 at 21:20

You are essentially after the most standard combinations function. As already pointed out, this can be done easily with itertools.combinations, or you can implement it yourself with recursion:

def combos(l, n):
    if n == 1:
        return [[e] for e in l]
    cs = []
    for i, e in enumerate(l):
        for c in combos(l[i+1:], n-1):
            cs.append([e] + c)
    return cs

and a test demonstrates its functionality:

>>> combos(['a', 'b', 'c'], 2)
[['a', 'b'], ['a', 'c'], ['b', 'c']]

How to write a function that uses a pair and returns sets of cardinality of 2 in Python?

2 Answers2