How can I have a custom list that will automatically sort itself following a "preferred" o-CodePudding

I'm trying to make a list that will try and stay in the "preferred" arrangement even though elements will get added and removed (although no new ones are introduced).

Let's say this is our preferred list:

preferred = ['hi', 'hello', 'welcome']

now if 'hello' gets removed, 'welcome' would be at [1].

If 'hello' gets added back, it should go back to [1] pushing back 'welcome' to [2] in the "preferred" position.

How can I do this?

CodePudding user response：

One solution is to use sorted with a custom key function that uses list.index to determine the preferred order:

preferred = ['hi', 'hello', 'welcome']

def sorter(value):
    try:
        return preferred.index(value)
    except ValueError:
        return -1  # this puts unknown values at the beginning in an arbitrary order

print(sorted([], key=sorter))                                      # []
print(sorted(['welcome'], key=sorter))                             # ['welcome']
print(sorted(['welcome', 'hello'], key=sorter))                    # ['hello', 'welcome']
print(sorted(['welcome', 'hello', 'hi'], key=sorter))              # ['hi', 'hello', 'welcome']
print(sorted(['welcome', 'hello', 'hi', 'hello'], key=sorter))     # ['hi', 'hello', 'hello', 'welcome']
print(sorted(['hi', 'hi', 'welcome', 'hello', 'hi'], key=sorter))  # ['hi', 'hi', 'hi', 'hello', 'welcome']
print(sorted(['hi', 'hello', 'goodbye', 'later'], key=sorter))     # ['goodbye', 'later', 'hi', 'hello']

Of course, with this solution you need to re-sort the list each time it changes.

CodePudding user response：

You would probably want to consider using a priority queue. In Python, priority queues can be implemented using the module heapq. This module essentially provides an implementation for the methods to create and manage a heap data structure.

The module can be used as such:

import heapq


preferred = ['hi', 'hello', 'welcome']

heapq.heapify(preferred)

# Add a new element
heapq.heappush(preferred, 'goodbye')

# Pop the smallest element from the heap and push a new one onto the heap
heapq.heapreplace(preferred, 'hey')

# Get all elements sorted
print(list(heapq.heappop(preferred) for _ in range(len(preferred))))  # Prints ['hello', 'hey', 'hi', 'welcome']

The downside of a heap is that we can not really get a random element from it based on index. We have to pop all the elements until we reach the one we were looking for.

The upside of using a heap is performance, mainly when newer elements inserted. Generally, the complexity of insertions is O(log n). Meanwhile, the smallest element from the heap can be retrieve in constant time (it is always the first element from the underlying list), while removing an element from the heap will also have a logarithmic complexity.

CodePudding user response：

You should apply your custom sort after each addition element to the list. For example, if you want to sort items by string length:

import functools

def cmp_items(a, b):
    if len(a) > len(b):
        return 1
    elif len(a) == len(b):
        return 0
    else:
        return -1

preferred = ['hello', 'hi', 'welcome']
preferred = sorted(preferred, key=functools.cmp_to_key(cmp_items))

After removing elements from the list you should do nothing.

CodePudding user response：

Here is the implementation for your question.

def functionName(preferred):
    length=len(preferred)
    while True:
        string=input("Enter a string: ")
        command=input("Enter a command: remove/add")
        if command.lower()=="remove":
            index=preferred.index(string)
            preferred.remove(string)
            print(preferred)
        if command.lower()=="add":
            if len(preferred)==length:
                print("You didn't remove before")
                break
            else:
                preferred.insert(index,string)
                print(preferred)
        
preferred=["hi",'hello','welcome']
functionName(preferred)

this is the custom output:

Enter a string: hello
Enter a command: remove/add remove
['hi', 'welcome']
Enter a string: hello
Enter a command: remove/add add
['hi', 'hello', 'welcome']
Enter a string: hi
Enter a command: remove/add add
You didn't remove before