# Help! I have a problem with lists!

Hello!

I am a real beginner in Sage, I have just started th use it. In fact this is my first programing language, so I have some difficulties with it... Now I needed a command, which determins all the k-element subset of [1,2,...,N]. Since I don't found a command like this, I decided to write a program... :-) And now I simple don't understand while my program doesn't work corrrectly! Could you explain me? It is a bit longish, so sorry for this.

def eve(A,N):
"""
the largest elem in the list A which can
be increased by 1, such that the resulting list contains only
different elements less than N. Originally
A should contain different elements in increasing order.
"""
ev = len(A)-1
while A[ev] == ev+N-len(A):
ev=ev-1
return ev

def rakovetkezo(A,N):
"""
Increases the eve(A,N)nt element by 1, and all the other elements
after this element are succesive natural numbers
"""
Q=A
ev=eve(Q,N)
x=Q[ev]
for i in range(ev,len(Q)):
Q[i]=x+i-ev+1
return Q

def reszhalmazok(N,k):
"""
It should (but it doesn't) return the k-element
subset of [1,2,...,N]
"""
X=range(k)
B=[range(k)]
ev=eve(X,N)
while ev != -1:
X=rakovetkezo(X,N)
B.append(X)
ev = eve(X,N)
return B


Now reszhalmazok(5,3) should return [[0,1,2], [0,1,3],...] but it returns something completely different, aaand I don't see why, and how could be improve it?

Katika

edit retag close merge delete

Sort by ยป oldest newest most voted

The reason why your program doesn't work is due to the line

Q = A


in rakovetkezo. When you do Q = A, you make Q point to the same object that A is pointing to. Then, when you change Q, you also change A. See the following:

sage: A = [1,2,3]
sage: Q = A
sage: id(Q)
88220880
sage: id(A)
88220880
sage: Q[0] = 100
sage: A
[100, 2, 3]


In order to make a copy of A, you can do something like

Q = A[:]


or

Q = list(A)


or

 from copy import copy
Q = copy(A)


Then your program will work just fine.

Sage also has a builtin class for working with with combinations which is a bit more fully-featured than itertools.combinations. Here are some examples of this.

sage: S = Combinations(range(5), 3); S
Combinations of [0, 1, 2, 3, 4] of length 3
sage: S.cardinality()
10
sage: S.random_element()
[0, 3, 4]
sage: S.list()
[[0, 1, 2], [0, 1, 3], [0, 1, 4], [0, 2, 3], [0, 2, 4], [0, 3, 4], [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]
sage: [x for x in S]
[[0, 1, 2], [0, 1, 3], [0, 1, 4], [0, 2, 3], [0, 2, 4], [0, 3, 4], [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]

more

Thank you! This was very surprising for me, however I have heard about pointers... I would never find this out! Now I will be more careful copying objects. :-)

( 2010-10-16 09:05:58 -0500 )edit

Use the built-in Python command itertools.combinations:

sage: import itertools
sage: L = [1..5]; L
[1, 2, 3, 4, 5]
sage: for s in itertools.combinations(L, 3):
....:     print s
....:
(1, 2, 3)
(1, 2, 4)
(1, 2, 5)
(1, 3, 4)
(1, 3, 5)
(1, 4, 5)
(2, 3, 4)
(2, 3, 5)
(2, 4, 5)
(3, 4, 5)

more

1

Thank you very much! Indeed it works, and I also found (reading your link it was easy), the command combinations... :-) It will help me a lot writing programs concerning subsets :-)

(Now I am more sure that SAGE works! Just still I don't see why that program written by me doesn't work as nice as the other programs of SAGE :-) )

( 2010-10-16 00:58:51 -0500 )edit