Subsets() with same element multiple times?

Essentially, I want to use:

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


[[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:
ListB.append(A)
sorted(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 close merge delete

Sort by ยป oldest newest most voted

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.

more

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

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

INPUT:

* "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?
Docstring:
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
"k".


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]]


HTH,

more