Sort string with integers and words without any change in their positions

Say I have a string a.

a = "12 I have car 8 200 a" 

I need to sort this string in such a way that the output should be

8 a car have 12 200 I 

ie, Sort the string in such a way that all words are in alphabetical order and all integers are in numerical order. Furthermore, if the nth element in the string is an integer it must remain an integer, and if it is a word it must remain a word.

This is what I tried.

a = "12 I have car 8 200 a"   def is_digit(element_):     """     Function to check the item is a number. We can make using of default isdigit function     but it will not work with negative numbers.     :param element_:     :return: is_digit_     """     try:         int(element_)         is_digit_ = True     except ValueError:         is_digit_ = False      return is_digit_    space_separated = a.split()  integers = [int(i) for i in space_separated if is_digit(i)] strings = [i for i in space_separated if i.isalpha()]  # sort list in place integers.sort() strings.sort(key=str.lower)  # This conversion to iter is to make use of next method. int_iter = iter(integers) st_iter = iter(strings)  final = [next(int_iter) if is_digit(element) else next(st_iter) if element.isalpha() else element for element in          space_separated]  print " ".join(map(str, final)) # 8 a car have 12 200 I 

I am getting the right output. But I am using two separate sorting function for sorting integers and the words(which I think is expensive).

Is it possible to do the entire sorting using a single sort function?.

6 Answers

Answers 1

numpy allows to write it more concisely, though doesn't eliminate the need for two separate sorts:

$ python3 Python 3.5.2 (default, Nov 23 2017, 16:37:01)  [GCC 5.4.0 20160609] on linux Type "help", "copyright", "credits" or "license" for more information. >>> import numpy as np >>> from numpy.core.defchararray import isdecimal, lower >>>  >>> s = "12 I have car 8 200 a" >>>  >>> a = np.array(s.split()) >>>  >>> integer_mask = isdecimal(a) >>> string_mask = ~integer_mask >>> strings = a[string_mask] >>>  >>> a[integer_mask] = np.sort(np.int_(a[integer_mask])) >>> a[string_mask]  = strings[np.argsort(lower(strings))] >>>  >>> ' '.join(a) '8 a car have 12 200 I' 

Answers 2

Is it possible to do the entire sorting using a single sort function?.

No, not really.

Why not? It turns out the answer is already in your code.

integers.sort() strings.sort(key=str.lower) 

Notice how you need to sort by two different functions here. The first is an integer sort, the second is a lowercase string sort. We could try something like this:

def get_sort_order(element):     try:         value = int(element)     except ValueError:         value = element.lower()     return value  a.sort(key=get_sort_order) 

But that doesn't work either; it just gives us the result

['8', '12', '200', 'a', 'car', 'have', 'I'] 

You could probably force this into a solution, but it isn't going to be pretty.

However, there is another point I'd like to address:

But I am using two separate sorting function for sorting integers and the words (which I think is expensive).

Sorting two distinct lists is basically always going to be faster anyway. To find out why, just look at the time complexity of the two tasks:

Assuming a list of length 1000, exactly half integer and half strings, and a sorting algorithm of O(nlog(n)):

One single sort: 1000 * log(1000) = 3000

Two separate sorts: 2 * (500 * log(500) = ~2699

So sorting the list in a single run is both more difficult to implement and slower!

Answers 3

It is possible in one sort, by applying a custom function within the 'sorted' method as a User described above. I have tried a simplified version for the same. The default 'sorted' method does the wonder with a little tweak. Hope it resolves your query.

import re  input = "12 I have car 8 200 a" splitted = input.split() s_lst=sorted(splitted, key=lambda a:int(a) if a.isdigit() else a.lower())  count_nos = re.findall(r'\d+',' '.join(s_lst)) str_index = len(count_nos) no_index = 0 result=[] for i in range(0,len(splitted)):     if splitted[i].isdigit():         result.append(s_lst[no_index])         no_index+=1     else:         result.append(s_lst[str_index])         str_index+=1 print ' '.join(result) 

Answers 4

You could do in one sort provided you write a custom function for comparision. The idea is to sort the words in ascending order and integer in descending order in the same list . Incase of word and integer is compared then treat the word as smaller compared to word.

And then for printing the final result increment the index for word if a word is found , decrement the index for integer if digit is found.

The below code works in python2:

a = "12 I have car 8 200 a"  def custom_compare(x,y):     if x.isdigit() and y.isdigit():         return int(y) - int(x) #do a descending order     if x.isdigit() and y.isdigit() == False:         return 1     if x.isdigit() == False and y.isdigit():         return -1     if x.isdigit() == False and y.isdigit() == False:         # do ascending order         if x.lower() == y.lower():             return 0         elif x.lower() < y.lower():             return -1         else:             return 1  original_list = a.split(" ") sorted_list = sorted(original_list, cmp=custom_compare)  result = [] integer_index = -1 string_index = 0 for word in original_list:     if word.isdigit():         result.append(sorted_list[integer_index])         integer_index = integer_index - 1     else:         result.append(sorted_list[string_index])         string_index = string_index + 1  result ['8', 'a', 'car', 'have', '12', '200', 'I'] 

Python 3: import functools

a = "12 I have car 8 200 a"  def custom_compare(x,y):     if x.isdigit() and y.isdigit():         return int(y) - int(x) #do a descending order     if x.isdigit() and y.isdigit() == False:         return 1     if x.isdigit() == False and y.isdigit():         return -1     if x.isdigit() == False and y.isdigit() == False:         # do ascending order         if x.lower() == y.lower():             return 0         elif x.lower() < y.lower():             return -1         else:             return 1  original_list = a.split(" ") sorted_list = sorted(original_list, key=functools.cmp_to_key(custom_compare))  result = [] integer_index = -1 string_index = 0 for word in original_list:     if word.isdigit():         result.append(sorted_list[integer_index])         integer_index = integer_index - 1     else:         result.append(sorted_list[string_index])         string_index = string_index + 1  result 

PS:The word comparison could be efficiently written. I am from C background and I am not sure of the pythonic way of comparison.

Answers 5

s = "2 is a A -3 car 11 I 0 a"  def magick(s):   s = s.split()    def reverse(tuples):     return [(a, b) for (b, a) in tuples]    def do_sort(tuples):     firsts  = [a for a, _ in tuples]     seconds = [a for _, a in tuples]     return list(zip(sorted(firsts), seconds))    def str_is_int(x):     try:       int(x)       return True     except:       return False    indexed = list(enumerate(s))    ints = do_sort([(int(x), ix) for (ix, x) in indexed if     str_is_int(x)])   strs = do_sort([(    x , ix) for (ix, x) in indexed if not str_is_int(x)])    return ' '.join([str(b) for _, b in sorted(reverse(ints+strs))])  print(magick(s)) 

Answers 6

This solution utilizes a single custom sorting algorithm, after grouping the original input into integers and strings:

def gt(a, b):   return a > b if isinstance(a, int) and isinstance(b, int) else a[0].lower() > b[0].lower()  def type_sort(d):    '''similar to bubble sort, but does not swap elements of different types.        For instance, type_sort([5, 3, 'b', 'a']) => [3, 5, 'a', 'b']    '''    for _ in d:      for i in range(len(d)-1):        _c = d[i]        _t = d[i+1]        if isinstance(_c, type(_t)):          if gt(_c, _t):            d[i+1] = _c            d[i] = _t    return d  def get_type(x):   return int(x) if x.isdigit() else x  def sort_in_place(s:str):   _s = list(map(get_type, s.split()))   new_s = type_sort([i for i in _s if isinstance(i, int)]+[i for i in _s if isinstance(i, str)])   ints = iter(i for i in new_s if isinstance(i, int))   strings = iter(i for i in new_s if isinstance(i, str))   return ' '.join(map(str, [next(ints) if isinstance(i, int) else next(strings) for i in _s]))  print(sort_in_place(a)) 

Output:

'8 a car have 12 200 I' 

Read More

map function run into infinite loop in 3.X

I'm currently studying iteration in python.

I have encountered the following code.

def myzip(*args):     iters = map(iter, args)     while iters:         res = [next(i) for i in iters]         print(res)         yield tuple(res)  list(myzip('abc', '1mnop')) 

When I run the code in 3.X, the code runs into a infinite loop, and prints

['a', '1'] [] [] [] ... 

The explanation I got from the author is

3.X map returns a one-shot iterable object instead of a list as in 2.X. In 3.X, as soon as we’ve run the list comprehension inside the loop once, iters will be exhausted but still True (and res will be []) forever.

But I am still struggling to understand what is happening and why it is happening.

And also, why is variable res only assigned value ('a', 'l') in the first iteration of while loop? Why is it not assigned ('b', 'm'), and then ('c', 'n') in second and third iteration?

4 Answers

Answers 1

Problem

But I am still struggling to understand what is happening and why it is happening.

And also, why is variable res only assigned value ('a', 'l') in the first iteration of while loop? res is always assigned an empty list [] afterwards. Why is it not assigned ('b', 'm'), and then ('c', 'n') in second and third iteration?

The reason the code you posted works in Python 2 while failing in Python 3, is because the built-in map returns an iterator in Python 3, rather than a list as it did in Python 2.

Of course this doesn't really explain much unless you know what an iterator is. Although I could go in-depth about what an iterator is exactly¹, the important part of iterators to understand here, is that: An iterator can only be iterated over once. Once you've iterated over an iterator once, it's exhausted. It's done. You can't use it anymore.²

When you iterate over the iters iterator in the list comprehension in your code, then iters is done and exhausted, and can no longer be used. So essentially all the list comprehension:

[next(i) for i in iters] 

does is grab the first item from each iterator in iters (which are 'a' and 'l'), and then store those in a list. On the next iteration of your while loop, iters can no longer be used, its empty. So empty list are yielded. That's why in the first list yielded you see 'a' and 'l', while other subsequent list are empty.

Lastly, the reason you're code degrades into an infinite loop, is because of the fact that an iterator object - even one that's been exhausted - will evaluate to True in a boolean context:

>>> it = map(str, [1, 2]) >>> next(it) '1' >>> next(it) '2' >>> # The `it` iterator is exhausted >>> next(it) Traceback (most recent call last):   File "<pyshell#17>", line 1, in <module>     next(it) StopIteration >>> bool(it) # but it still evaluates to `True` in a boolean context True >>>  

Solution

The simplest solution to this problem is to cast the iterator returned by map into a list, since list objects support being iterated over multiple times:

>>> def custom_zip(*args):     iters = list(map(iter, args))     while iters:         yield tuple([next(it) for it in iters])   >>> list(custom_zip('abc', [1, 2, 3])) [('a', 1), ('b', 2), ('c', 3)] >>> list(custom_zip('def', [4, 5, 6])) [('d', 4), ('e', 5), ('f', 6)] >>> list(custom_zip([1, 2, 3], [1, 4, 9], [1, 8, 27])) [(1, 1, 1), (2, 4, 8), (3, 9, 27)] >>>  

As @Chris_Rands also noted, although the above code works, a more idiomatic way to implement a custom zip function in Python 3+ would be:

def custom_zip(*args):     return map(lambda *x: x, *args) 

---

¹_{As a side note, if you would like to understand what an iterator is in-depth, see the question What exactly are Python's iterator, iterable, and iteration protocols?}

²_{For a more complete look into why exhausted iterators evaluate to True, see the question How can I get generators/iterators to evaluate as False when exhausted?}

Answers 2

def myzip(*args):     iters = list(map(iter,args))     while iters :         res = [next(i) for i in iters]         print(res)         yield tuple(res)  print (list(myzip('abc', '1mnop','yada'))) 

Output

['a', '1', 'y'] ['b', 'm', 'a'] ['c', 'n', 'd'] [('a', '1', 'y'), ('b', 'm', 'a'), ('c', 'n', 'd')] 

Reason as provided by Christian Dean.

Answers 3

the reason the code you posted works in Python 2 but mot in Python 3, is because the built-in map returns an iterator in Python 3, but returns a list in Python 2.

Answers 4

Please check if this is what you want:

def myzip(*args):     iters = map(iter, args)     while iters:         res = [i for i in next(iters)]         yield tuple(res)  list(myzip('abc', '1mnop')) 

Read More

create library to override operator()* of iterator - risk dangling pointer

I am trying to create my own boost::adaptors::transformed.
Here is the related boost code.

Here is its usage (modified from a SO answer by LogicStuff):-

C funcPointer(B& b){      //"funcPointer" is function convert from "B" to "C"     return instance-of-C }  MyArray<B> test;  //<-- any type, must already has begin() & end()  for(C c : test | boost::adaptor::transformed(funcPointer)) {     //... something .... } 

The result will be the same as :-

for(auto b : test) {     C c = funcPointer(b);     //... something ... } 

My Attempt

I created CollectAdapter that aim to work like boost::adaptor::transformed.
It works OK in most common cases.

Here is the full demo and back up. (same as below code)

The problematic part is CollectAdapter - the core of my library.
I don't know whether I should cache the collection_ by-pointer or by-value.

CollectAdapter encapsulates underlying collection_ (e.g. pointer to std::vector<>) :-

template<class COLLECTION,class ADAPTER>class CollectAdapter{     using CollectAdapterT=CollectAdapter<COLLECTION,ADAPTER>;     COLLECTION* collection_;    //<---- #1  problem? should cache by value?     ADAPTER adapter_;           //<---- = func1 (or func2)     public: CollectAdapter(COLLECTION& collection,ADAPTER adapter){         collection_=&collection;         adapter_=adapter;     }     public: auto begin(){         return IteratorAdapter<             decltype(std::declval<COLLECTION>().begin()),             decltype(adapter_)>             (collection_->begin(),adapter_);     }     public: auto end(){ ..... } }; 

IteratorAdapter (used above) encapsulates underlying iterator, change behavior of operator* :-

template<class ITERATORT,class ADAPTER>class IteratorAdapter : public ITERATORT {     ADAPTER adapter_;     public: IteratorAdapter(ITERATORT underlying,ADAPTER adapter) :         ITERATORT(underlying),         adapter_(adapter)     {   }     public: auto operator*(){         return adapter_(ITERATORT::operator*());     } }; 

CollectAdapterWidget (used below) is just a helper class to construct CollectAdapter-instance.

It can be used like:-

int func1(int i){   return i+10;   } int main(){     std::vector<int> test; test.push_back(5);     for(auto b:CollectAdapterWidget::createAdapter(test,func1)){         //^ create "CollectAdapter<std::vector<int>,func1>" instance          //here, b=5+10=15     } }   

Problem

The above code works OK in most cases, except when COLLECTION is a temporary object.

More specifically, dangling pointer potentially occurs when I create adapter of adapter of adapter ....

int func1(int i){   return i+10;    } int func2(int i){   return i+100;   } template<class T> auto utilityAdapter(const T& t){     auto adapter1=CollectAdapterWidget::createAdapter(t,func1);     auto adapter12=CollectAdapterWidget::createAdapter(adapter1,func2);     //"adapter12.collection_" point to "adapter1"     return adapter12;     //end of scope, "adapter1" is deleted     //"adapter12.collection_" will be dangling pointer } int main(){     std::vector<int> test;     test.push_back(5);     for(auto b:utilityAdapter(test)){         std::cout<< b<<std::endl;   //should 5+10+100 = 115     } } 

This will cause run time error. Here is the dangling-pointer demo.

In the real usage, if the interface is more awesome, e.g. use | operator, the bug will be even harder to be detected :-

//inside "utilityAdapter(t)" return t|func1;        //OK! return t|func1|func2;  //dangling pointer 

Question

How to improve my library to fix this error while keeping performance & robustness & maintainablilty near the same level?

In other words, how to cache data or pointer of COLLECTION (that can be adapter or real data-structure) elegantly?

Alternatively, if it is easier to answer by coding from scratch (than modifying my code), go for it. :)

My workarounds

The current code caches by pointer.
The main idea of workarounds is to cache by value instead.

Workaround 1 (always "by value")

Let adapter cache the value of COLLECTION.
Here is the main change:-

COLLECTION collection_;    //<------ #1  //changed from   .... COLLECTION* collection_; 

Disadvantage:-

• Whole data-structure (e.g. std::vector) will be value-copied - waste resource.
  (when use for std::vector directly)

Workaround 2 (two versions of library, best?)

I will create 2 versions of the library - AdapterValue and AdapterPointer.
I have to create related classes (Widget,AdapterIterator,etc.) as well.

• AdapterValue - by value. (designed for utilityAdapter())
• AdapterPointer - by pointer. (designed for std::vector)

Disadvantage:-

• Duplicate code a lot = low maintainability
• Users (coders) have to be very conscious about which one to pick = low robustness

Workaround 3 (detect type)

I may use template specialization that do this :-

If( COLLECTION is an "CollectAdapter" ){ by value }   Else{ by pointer }     

Disadvantage:-

• Not cooperate well between many adapter classes.
  They have to recognize each other : recognized → cache by value.

Sorry for very long post.

0 Answers

Read More

PYTHON 2.7 - Modifying List of Lists and Re-Assembling Without Mutating

I currently have a list of lists that looks like this:

My_List = [[This, Is, A, Sample, Text, Sentence] [This, too, is, a, sample, text] [finally, so, is, this, one]] 

Now what I need to do is "tag" each of these words with one of 3, in this case arbitrary, tags such as "EE", "FF", or "GG" based on which list the word is in and then reassemble them into the same order they came in. My final code would need to look like:

GG_List = [This, Sentence] FF_List = [Is, A, Text] EE_List = [Sample]  My_List = [[(This, GG), (Is, FF), (A, FF), (Sample, "EE), (Text, FF), (Sentence, GG)] [*same with this sentence*] [*and this one*]] 

I tried this by using for loops to turn each item into a dict but the dicts then got rearranged by their tags which sadly can't happen because of the nature of this thing... the experiment needs everything to stay in the same order because eventually I need to measure the proximity of tags relative to others but only in the same sentence (list).

I thought about doing this with NLTK (which I have little experience with) but it looks like that is much more sophisticated then what I need and the tags aren't easily customized by a novice like myself.

I think this could be done by iterating through each of these items, using an if statement as I have to determine what tag they should have, and then making a tuple out of the word and its associated tag so it doesn't shift around within its list.

I've devised this.. but I can't figure out how to rebuild my list-of-lists and keep them in order :(.

for i in My_List: #For each list in the list of lists     for h in i:   #For each item in each list          if h in GG_List:  # Check for the tag             MyDicts = {"GG":h for h in i}  #Make Dict from tag + word 

Thank you so much for your help!

2 Answers

Answers 1

Putting the tags in a dictionary would work:

My_List = [['This', 'Is', 'A', 'Sample', 'Text', 'Sentence'],            ['This', 'too', 'is', 'a', 'sample', 'text'],            ['finally', 'so', 'is', 'this', 'one']] GG_List = ['This', 'Sentence'] FF_List = ['Is', 'A', 'Text'] EE_List = ['Sample']  zipped = zip((GG_List, FF_List, EE_List), ('GG', 'FF', 'EE')) tags = {item: tag for tag_list, tag in zipped for item in tag_list} res = [[(word, tags[word]) for word in entry if word in tags] for entry in My_List] 

Now:

>>> res [[('This', 'GG'),   ('Is', 'FF'),   ('A', 'FF'),   ('Sample', 'EE'),   ('Text', 'FF'),   ('Sentence', 'GG')],  [('This', 'GG')],  []] 

Answers 2

Dictionary works by key-value pairs. Each key is assigned a value. To search the dictionary, you search the index by the key, e.g.

>>> d = {1:'a', 2:'b', 3:'c'} >>> d[1] 'a' 

In the above case, we always search the dictionary by its keys, i.e. the integers.

In the case that you want to assign the tag/label to each word, you are searching by the key word and finding the "value", i.e. the tag/label, so your dictionary would have to look something like this (assuming that the strings are words and numbers as tag/label):

>>> d = {'a':1, 'b':1, 'c':3} >>> d['a'] 1 >>> sent = 'a b c a b'.split() >>> sent ['a', 'b', 'c', 'a', 'b'] >>> [d[word] for word in sent] [1, 1, 3, 1, 1] 

This way the order of the tags follows the order of the words when you use a list comprehension to iterate through the words and find the appropriate tags.

So the problem comes when you have the initial dictionary indexed with the wrong way, i.e. key -> labels, value -> words, e.g.:

>>> d = {1:['a', 'd'], 2:['b', 'h'], 3:['c', 'x']} >>> [d[word] for word in sent] Traceback (most recent call last):   File "<stdin>", line 1, in <module> KeyError: 'a' 

Then you would have to reverse your dictionary, assuming that all elements in your value lists are unique, you can do this:

>>> from collections import ChainMap >>> d = {1:['a', 'd'], 2:['b', 'h'], 3:['c', 'x']} >>> d_inv = dict(ChainMap(*[{value:key for value in values} for key, values in d.items()])) >>> d_inv {'h': 2, 'c': 3, 'a': 1, 'x': 3, 'b': 2, 'd': 1} 

But the caveat is that ChainMap is only available in Python3.5 (yet another reason to upgrade your Python ;P). For Python <3.5, solutions, see How do I merge a list of dicts into a single dict?.

So going back to the problem of assigning labels/tags to words, let's say we have these input:

>>> d = {1:['a', 'd'], 2:['b', 'h'], 3:['c', 'x']} >>> sent = 'a b c a b'.split() 

First, we invert the dictionary (assuming that there're one to one mapping for every word and its tag/label:

>>> d_inv = dict(ChainMap(*[{value:key for value in values} for key, values in d.items()])) 

Then, we apply the tags to the words through a list comprehension:

>>> [d_inv[word] for word in sent] [1, 2, 3, 1, 2] 

And for multiple sentences:

>>> sentences = ['a b c'.split(), 'h a x'.split()] >>> [[d_inv[word] for word in sent] for sent in sentences] [[1, 2, 3], [2, 1, 3]] 

Read More