Ask Your Question

Subsets() with same element multiple times?

asked 2022-08-22 02:47:49 +0200

Eric Snyder gravatar image

updated 2022-08-22 02:48:25 +0200

Essentially, I want to use:

ListA = [1,2,3]
S = some_function(ListA, 2)

And receive in return

[[1,1], [1,2], [1,3], [2,2], [2,3], [3,3]]

Theoretically, some_function() ought to be Subsets() with some options, but that doesn't seem available. Is there a good way to do this other than a multiple for loop? You can work around how Subsets() works with:

ListB = []
for i in ListA:
    for j in ListA:
        A = sorted([i,j])
        if A not in ListB:

But that gets tedious (and probably time-consuming) when you want 6-element subsets--and extra annoying if you want to be able to change the length with a variable. It seems like this ought to be an included functionality; what some_function() am I missing?

edit retag flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted

answered 2022-08-22 04:21:29 +0200

updated 2022-08-22 22:44:56 +0200

Python's itertools module has lots of useful functions, including:

sage: import itertools
sage: ListA = [1,2,3]
sage: S = itertools.combinations_with_replacement(ListA, 2)
sage: list(S)
[(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]

Edit: If you want to use Sage-specific code, you can use Combinations. This will return duplicates only if they appear in the original list, so you can use ListA * n to get n copies of your list, and then choose combinations from that:

sage: S = Combinations(ListA * 2, 2)
sage: list(S)
[[1, 1], [1, 2], [1, 3], [2, 2], [2, 3], [3, 3]]

The itertools versions seem to be faster, in my limited testing.

edit flag offensive delete link more

answered 2022-08-22 11:02:05 +0200

Emmanuel Charpentier gravatar image

Well... Let's try to be lazy, and reuse work already done :

sage: subsets?
   Iterator over the *list* of all subsets of the iterable X, in no
   particular order. Each list appears exactly once, up to order.


   * "X" - an iterable

   OUTPUT: iterator of lists

So, what's wrong with :

sage: [u for u in subsets(ListA) if len(u) == 2]
[[1, 2], [1, 3], [2, 3]]

Of course, the subsets operator will generate all subsets of ListA. It might be interesting to write a specialized generator...

OTOH, someone already did the work (and probably better than I can do) :

sage: Subsets?
   Return the combinatorial class of the subsets of the finite set
   "s". The set can be given as a list, Set or any iterable
   convertible to a set. Alternatively, a non-negative integer n can
   be provided in place of "s"; in this case, the result is the
   combinatorial class of the subsets of the set \{1,2,...,n\} (i.e.
   of the Sage "range(1,n+1)").

   A second optional parameter "k" can be given. In this case,
   "Subsets" returns the combinatorial class of subsets of "s" of size

Therefore :

sage: list(Subsets(ListA, 2))
[{1, 2}, {1, 3}, {2, 3}]

Beware : the returned elements are Sets (and not sets). If you insist on lists :

sage: list(map(list, Subsets(ListA, 2)))
[[1, 2], [1, 3], [2, 3]]


edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2022-08-22 02:47:49 +0200

Seen: 153 times

Last updated: Aug 22 '22