Sorting by item_in_another _list

[Cameron Walsh]

Hi,

I have two lists, A and B, such that B is a subset of A.

I wish to sort A such that the elements in B are at the beginning of A,
and keep the existing order otherwise, i.e. stable sort. The order of
elements in B will always be correct.

for example:

A = [0,1,2,3,4,5,6,7 ,8,9,10]
B = [2,3,7,8]

desired_result = [2,3,7,8,0,1,4,5 ,6,9,10]
At the moment I have defined a comparator function:

def sort_by_in_list (x,y):
ret = 0
if x in B:
ret -= 1
if y in B:
ret += 1
return ret

and am using:

A.sort(sort_by_ in_list)

which does produce the desired results.

I do now have a few questions:

1.) Is this the most efficient method for up to around 500 elements?
If not, what would be better?
2.) This current version does not allow me to choose a different list
for B. Is there a bind_third function of some description that I could
use to define a new function with 3 parameters, feed it the third (the
list to sort by), and have the A.sort(sort_by_ in_list) provide the other
2 variables?
Regards to all,

Cameron.

[Cameron Walsh]

Cameron Walsh wrote:

Hi,

I have two lists, A and B, such that B is a subset of A.

I wish to sort A such that the elements in B are at the beginning of A,
and keep the existing order otherwise, i.e. stable sort. The order of
elements in B will always be correct.

for example:

A = [0,1,2,3,4,5,6,7 ,8,9,10]
B = [2,3,7,8]

desired_result = [2,3,7,8,0,1,4,5 ,6,9,10]
At the moment I have defined a comparator function:

def sort_by_in_list (x,y):
ret = 0
if x in B:
ret -= 1
if y in B:
ret += 1
return ret

and am using:

A.sort(sort_by_ in_list)

which does produce the desired results.

I do now have a few questions:

1.) Is this the most efficient method for up to around 500 elements? If
not, what would be better?
2.) This current version does not allow me to choose a different list
for B. Is there a bind_third function of some description that I could
use to define a new function with 3 parameters, feed it the third (the
list to sort by), and have the A.sort(sort_by_ in_list) provide the other
2 variables?
Regards to all,

Cameron.

Well I found an answer to the second question with the following:

>>A=[0,1,2,3,4,5,6,7 ,8,9,10]
B=[2,3,7,8]
def sort_by_in_list (in_list):

def ret_function(x, y):
ret = 0
if x in in_list:
ret -= 1
if y in in_list:
ret += 1
return ret
return ret_function

>>A.sort(sort_b y_in_list(B))
A

[2, 3, 7, 8, 0, 1, 4, 5, 6, 9, 10]
Hope it helps someone,

Cameron.

[Paul McGuire]

"Cameron Walsh" <ca***********@ gmail.comwrote in message
news:eh******** **@enyo.uwa.edu .au...

Hi,

I have two lists, A and B, such that B is a subset of A.

I wish to sort A such that the elements in B are at the beginning of A,
and keep the existing order otherwise, i.e. stable sort. The order of
elements in B will always be correct.

for example:

A = [0,1,2,3,4,5,6,7 ,8,9,10]
B = [2,3,7,8]

desired_result = [2,3,7,8,0,1,4,5 ,6,9,10]
At the moment I have defined a comparator function:

def sort_by_in_list (x,y):
ret = 0
if x in B:
ret -= 1
if y in B:
ret += 1
return ret

and am using:

A.sort(sort_by_ in_list)

which does produce the desired results.

I do now have a few questions:

1.) Is this the most efficient method for up to around 500 elements? If
not, what would be better?
2.) This current version does not allow me to choose a different list for
B. Is there a bind_third function of some description that I could use to
define a new function with 3 parameters, feed it the third (the list to
sort by), and have the A.sort(sort_by_ in_list) provide the other 2
variables?

Think in Python. Define a function to take the list, and have that function
return the proper comparison function. This gives me the chance to also
convert the input list to a set, which will help in scaling up my list to
hundreds of elements. See below.

-- Paul
def sort_by_in_list (reflist):
reflist = set(reflist)
def sort_by_in_list _(x,y):
ret = 0
if x in reflist: ret -= 1
if y in reflist: ret += 1
return ret
return sort_by_in_list _

A = [0,1,2,3,4,5,6,7 ,8,9,10]
B = [2,3,7,8]
A.sort( sort_by_in_list (B) )
print A

Gives:
[2, 3, 7, 8, 0, 1, 4, 5, 6, 9, 10]

[Cameron Walsh]

Paul McGuire wrote:

"Cameron Walsh" <ca***********@ gmail.comwrote in message
news:eh******** **@enyo.uwa.edu .au...

>Hi,

I have two lists, A and B, such that B is a subset of A.

I wish to sort A such that the elements in B are at the beginning of A,
and keep the existing order otherwise, i.e. stable sort. The order of
elements in B will always be correct.

for example:

A = [0,1,2,3,4,5,6,7 ,8,9,10]
B = [2,3,7,8]

desired_resu lt = [2,3,7,8,0,1,4,5 ,6,9,10]
At the moment I have defined a comparator function:

def sort_by_in_list (x,y):
ret = 0
if x in B:
ret -= 1
if y in B:
ret += 1
return ret

and am using:

A.sort(sort_by _in_list)

which does produce the desired results.

I do now have a few questions:

1.) Is this the most efficient method for up to around 500 elements? If
not, what would be better?
2.) This current version does not allow me to choose a different list for
B. Is there a bind_third function of some description that I could use to
define a new function with 3 parameters, feed it the third (the list to
sort by), and have the A.sort(sort_by_ in_list) provide the other 2
variables?

Think in Python. Define a function to take the list, and have that function
return the proper comparison function. This gives me the chance to also
convert the input list to a set, which will help in scaling up my list to
hundreds of elements. See below.

-- Paul
def sort_by_in_list (reflist):
reflist = set(reflist)
def sort_by_in_list _(x,y):
ret = 0
if x in reflist: ret -= 1
if y in reflist: ret += 1
return ret
return sort_by_in_list _

A = [0,1,2,3,4,5,6,7 ,8,9,10]
B = [2,3,7,8]
A.sort( sort_by_in_list (B) )
print A

Gives:
[2, 3, 7, 8, 0, 1, 4, 5, 6, 9, 10]

Looks like our answers crossed-over. Must learn about sets in Python...

Thanks very much,

Cameron.

[Paul Rubin]

Cameron Walsh <ca***********@ gmail.comwrites :

for example:

A = [0,1,2,3,4,5,6,7 ,8,9,10]
B = [2,3,7,8]

desired_result = [2,3,7,8,0,1,4,5 ,6,9,10]

How about:

desired_result = B + sorted(x for x in A if x not in B)

[ZeD]

Paul Rubin wrote:

>A = [0,1,2,3,4,5,6,7 ,8,9,10]
B = [2,3,7,8]

desired_resu lt = [2,3,7,8,0,1,4,5 ,6,9,10]

How about:

desired_result = B + sorted(x for x in A if x not in B)

this. is. cool.

--
Under construction

[Paul Rubin]

ZeD <vi***********@ gmail.comwrites :

desired_result = B + sorted(x for x in A if x not in B)

this. is. cool.

Actually it's better to use a set if B is large:

B2 = set(B)
desired_result = B + sorted(x for x in A if x not in B2)

That avoids a linear search through B for each element of A.

[Fredrik Lundh]

Paul Rubin wrote:

>for example:

A = [0,1,2,3,4,5,6,7 ,8,9,10]
B = [2,3,7,8]

desired_resu lt = [2,3,7,8,0,1,4,5 ,6,9,10]

How about:

desired_result = B + sorted(x for x in A if x not in B)

assuming that "keep the existing order" means what it says, you might as
well replace "sorted" with a list comprehension.

</F>

[Paul Rubin]

Fredrik Lundh <fr*****@python ware.comwrites:

desired_result = B + sorted(x for x in A if x not in B)

assuming that "keep the existing order" means what it says, you might
as well replace "sorted" with a list comprehension.

Hmm. I didn't read it that way, but yeah, if that's what the OP meant
then the sort could be skipped. I thought he just wanted a stable
sort, which the sorting primitives now promise.

[J. Clifford Dyer]

ZeD wrote:

Paul Rubin wrote:

>>A = [0,1,2,3,4,5,6,7 ,8,9,10]
B = [2,3,7,8]

desired_resul t = [2,3,7,8,0,1,4,5 ,6,9,10]

How about:

desired_result = B + sorted(x for x in A if x not in B)

this. is. cool.

Cool, yes, but I'm not entirely sure it does what the OP wanted. Partly
because I'm not entirely sure what the OP wanted. Counter example:

Given these variables:

A = [0,1,2,3,4,5,6,8 ,9,10] # Note 7 is missing
B = [2,3,7,8]

which of the following should the function yield?

desired_result = [2,3,7,8,0,1,4,5 ,6,9,10]
desired_result2 = [2,3,8,0,1,4,5,6 ,9,10]

The fact that we are ostensibly sorting A makes me thing it should be
the latter, but the example given was ambiguous. If we are in fact
looking for desired_result2 , maybe we should use:

result = [ x for x in B if x in A ] + [ x for x in A if X not in B ]

or like the sibling post suggests: substitute set(A) and set(B) for the
"in" argument in each comprehension.

Cheers,
Cliff