how to do proper subclassing?

[=?iso-8859-1?q?Jonas=20Koelker?=]

Hello there.

I'm new to this list (/me welcomes himself).

anyways, I'm having doubts about how to subclass
properly. The big picture is that I want to handle
permutations. As we all know, two popular notation
forms exist: products of disjoint cycles ("(0 1 3)(2
4)") and 2*length matrices with the identity
permutation as the first line ([0 1 2 3 4] over [1 3 4
0 2]). I find the latter more appropriate, since it's
easy to store as a list (one can skip the first line,
assuming it's _always_ the identity).

However, I want the permutation to act like a list, in
all those cases where I don't override the operations.
For example, assuming permfooation is the above
permutation [1 3 4 0 2], permfooation[1:3] should
return [3,4]. How is this done? Do I have to actually
implement a slice-mechanism in the permutation class?

thanks,

-- Jonas Kölker





___________________________________________________________ALL-NEW Yahoo! Messenger - all new features - even more fun! http://uk.messenger.yahoo.com

 

[Larry Bates]

I think you want to have permfooation actually be
a list. If you do then permfooation[1:3} will in
fact return a list [3,4]. If the permutation is
actually stored as:

[0 1 2 3 4]
[1 3 4 0 2]

You can get them into lists with:

f=open(inputfile)
lines=f.readlines()
f.close()
l=0
for line in lines:
if l % 2 == 0: continue # skip first lines
l+=1
permfooation=[int(x) for x in line[1:-1].split()]

print permfooation[1:3]

Now you are probably going to want to wrap this into
a class for easier use.

HTH,
Larry Bates
Syscon, Inc.

Hello there.

I'm new to this list (/me welcomes himself).

anyways, I'm having doubts about how to subclass
properly. The big picture is that I want to handle
permutations. As we all know, two popular notation
forms exist: products of disjoint cycles ("(0 1 3)(2
4)") and 2*length matrices with the identity
permutation as the first line ([0 1 2 3 4] over [1 3 4
0 2]). I find the latter more appropriate, since it's
easy to store as a list (one can skip the first line,
assuming it's _always_ the identity).

However, I want the permutation to act like a list, in
all those cases where I don't override the operations.
For example, assuming permfooation is the above
permutation [1 3 4 0 2], permfooation[1:3] should
return [3,4]. How is this done? Do I have to actually
implement a slice-mechanism in the permutation class?

thanks,

-- Jonas Kölker





___________________________________________________________ALL-NEW Yahoo!

Messenger - all new features - even more fun! http://uk.messenger.yahoo.com

 

[Peter Otten]

Hello there.

I'm new to this list (/me welcomes himself).

anyways, I'm having doubts about how to subclass
properly. The big picture is that I want to handle
permutations. As we all know, two popular notation
forms exist: products of disjoint cycles ("(0 1 3)(2
4)") and 2*length matrices with the identity
permutation as the first line ([0 1 2 3 4] over [1 3 4
0 2]). I find the latter more appropriate, since it's
easy to store as a list (one can skip the first line,
assuming it's _always_ the identity).

However, I want the permutation to act like a list, in
all those cases where I don't override the operations.
For example, assuming permfooation is the above
permutation [1 3 4 0 2], permfooation[1:3] should
return [3,4]. How is this done? Do I have to actually
implement a slice-mechanism in the permutation class?

You already answered your question in the subject - you want a subclass of
list:
.... def __init__(self, n):
.... list.__init__(self, range(n))
.... def __call__(self, i, k):
.... self, self[k] = self[k], self
.... return self
....

p = Perm(5)
p [0, 1, 2, 3, 4]
p(0,4)(2,4)(0,1)(2,3)(1,2) [1, 3, 4, 0, 2]
p[1:2] [3]
p[1:3]

[3, 4]

Just in case you need it later, there is a special method for every
operator, e. g. __getitem__() for obj[sliceOrIndex], __mul__() for
multiplication etc. Write one for the class in question and it will grow
the corresponding operation. In the above example I have made the class
"callable" (i. e. its instances can behave like a function) by adding the
__call__() method. By returning self I ensure that you can chain these
calls. As you may know, this is not the way the list.sort() method behaves,
so this is probably bad style for methods mutating the original instance.

As to __getitem__(), I think the easiest way to see what happens inside is
provided by the following snippet:
.... def __getitem__(self, i):
.... return i
....

C()[1] 1
C()[1:2] slice(1, 2, None)
C()[1:2:3]

slice(1, 2, 3)

I. e. a typical minimal __getitem__() has to test whether it receives a
slice or an integer using isinstance().

Peter

 

[Christopher T King]

I'm new to this list (/me welcomes himself).
Welcome!

However, I want the permutation to act like a list, in
all those cases where I don't override the operations.
For example, assuming permfooation is the above
permutation [1 3 4 0 2], permfooation[1:3] should
return [3,4]. How is this done? Do I have to actually
implement a slice-mechanism in the permutation class?

I'm not sure exactly how your permutation class is implemented, so I can't
give you a precise answer, but in general, there are three ways to do
this, each method having benefits and drawbacks:

1) Implement your class as a subclass of list.

Using this method, your class would store its list data in itself (in
self, actually), since it is effectively a list. The __getitem__ method
needed to implement slicing will be inherited from list, and no further
work will need to be done. This method works best if you're only altering
the behaviour of a list slightly (e.g. transforming all items in a
particular way), but may not be well suited to objects that shouldn't
otherwise act like lists.

2) Store your data in a list, and delegate __getitem__.

Using this method, your class would store its list data in an attribute
(say self.data). To implement slicing, you can simply define your class's
__getitem__ method like this:

def __getitem__(self,i):
return self.data

assuming self.data contains the list data to which you want to provide
access. This is the easiest method if all you want to implement is
slicing.

3) Implement __getitem__ yourself.

You should only need to do this if the data you want to slice is not
available in a readily slicable form (perhaps you generate it on the fly).
Implementing __getitem__ is easy; here is a general template you can use:

def __getitem__(self,i):
if isinstance(i,slice):
return self.make_a_slice_and_return_a_list(i.start,i.stop,i.step)
else:
return self.get_an_item_at_index(i)

__getitem__ is passed either a slice object (in the case of slicing) or
an integer (in the case of indexing). The start, stop, and step
attributes of the slice object return what you'd expect, or None if they
weren't specified. The method slice.indices(length) will compute "actual"
slice indices for a sequence of the given length in the case of missing,
negative, or out-of-bounds indices, returning a tuple (start, stop,
stride).

Hope this helps.

 

[Peter Otten]

I'm new to this list (/me welcomes himself).

Jonas, I suggest that you post follow-ups vaguely on topic on c.l.py. That
gives you the chance for answers that I (for example) don't know about or
care to give as well as corrections or a second opinion.

[Jonas via email]

class Perm(list):

... def __init__(self, n):
... list.__init__(self, range(n))
... def __call__(self, i, k):
... self, self[k] = self[k], self
... return self
...

p = Perm(5)
p

[0, 1, 2, 3, 4]

p(0,4)(2,4)(0,1)(2,3)(1,2)

[1, 3, 4, 0, 2]

p[1:2]
[3]

p[1:3]

[3, 4]

thanks, this looks about right (slaps himself on the
forehead - "you DO know how init works!")... :]

also, p(0,4)(2,4)(0,1)(2,3)(1,2) looks really neat and
math'ish

Just in case you need it later, there is a special
method for every operator, e. g. __getitem__() for
obj[sliceOrIndex], __mul__() for multiplication etc.

Yeah, I knew that. I might make __int__() convert the
perm to a ranking number in linear time. See

My mentioning of special methods doesn't mean that I think they are always
the best choice. I would prefer both p.rank() and rank(p) over int(p).

http://www.cs.uvic.ca/~ruskey/Publications/RankPerm.html

.. don't worry, I can implement it myself.

Don't worry, I won't

btw, if I want to set the "list part" of the perm, how
do I do that?

p[:] = [1, 2, 3, 4, 5]
p[:2] = p[1], p[0]
p[2] = [99]

If you want to ensure that the permutation is still valid after assignment
you have to write your own __setitem__() method.

p = [4,0,3,2,1] would turn p into a list.
p = perm(5)(0,4)(2,4)(0,1)(2,3)(1,2) is valid (right?)
but time consuming.

That was just for fun... most likely faster than

while p != [4,0,3,2,1]: random.shuffle(p)

I'd say it'd be easier/better to implement it as:

... def __init__(self, n):
... list.__init__(self, n)

The good if __init__() does nothing but call the base class'
__init__(), you need not write one at all.

... def __call__(self, i, k):
... self, self[k] = self[k], self
... return self

p = Perm([4, 0, 3, 2, 1])

... anyways, thanks

You're welcome.

Peter