Ask Your Question
1

Help! I have a problem with lists!

asked 2010-10-16 05:42:24 +0100

updated 2010-10-16 14:28:04 +0100

Mike Hansen gravatar image

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 flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted
4

answered 2010-10-16 14:26:54 +0100

Mike Hansen gravatar image

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]]
edit flag offensive delete link more

Comments

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. :-)

Katika gravatar imageKatika ( 2010-10-16 16:05:58 +0100 )edit
2

answered 2010-10-16 07:08:39 +0100

mvngu gravatar image

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)
edit flag offensive delete link more

Comments

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 :-) )

Katika gravatar imageKatika ( 2010-10-16 07:58:51 +0100 )edit

Your Answer

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

Add Answer

Question Tools

Stats

Asked: 2010-10-16 05:42:24 +0100

Seen: 475 times

Last updated: Oct 16 '10