# 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 16:05:58 +0100 )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 07:58:51 +0100 )edit