0

I am not a python expert.

I am trying to implement a solution for a K-Coloring interval problem. Only using the python standard library, so no numpy,.

What i want to achieve :

So i have a sorted list of elements, and in each loop iteration i need to exclude multiple elements , so that in the next iteration the loop Continues to work on the sorted subset that resulted from the last iteration. In each iteration i am accessing the indexes using binary search algorithm, and the list must always be sorted when worked on.

I've tried using array.pop(index) but my solution was slow and not efficient for a list of 100000 elements since it has O(n) complexity according to https://wiki.python.org/moin/TimeComplexity with n being number of elements in the list.

I've tried storing the inputs in a set() and work on them, however since in every iteration i have to execute binary search algorithm i can't store them because i will be needing to access elements by index for the sake of binary search, which is not possible in a set TypeError: 'set' object is not subscriptable.

Ex:

Input is a list sorted in ascending order according to the second item of each subarray.

arr = [[0, -1, 0], [1, 4, 0], [3, 5, 0], [0, 6, 0], [4, 7, 0], [3, 7, 0], [5, 9, 0], [6, 10, 0]]

for i in range(len(arr)) :

   x = binarysearch(arr, value) #returns an index

   while x > 0 :
      helper = x
      array.exclude(x)
      x = binarysearch(arr, arr[helper][0]) #returns an index

I don't want all the arr[x] that were excluded from the last iteration to be included in the current one.

Any ideas of thoughts would be much appreciated.

Thanks in advance

kollegah
  • 31
  • 6
  • 5
    please provide [mcve] – DeepSpace Mar 03 '20 at 15:37
  • `O(n)` sounds about the fastest you can get if you need to operate on individual elements. But your description sounds more like an `O(n^2)` problem ("... in each loop iteration i need to exclude multiple elements , so that in the next iteration ..."): loops over loops. – 9769953 Mar 03 '20 at 15:41
  • AFAIK there is no container in standard python that achieves both random access and deletion in less than `O(n)`. You could do this with `O(log(n))` with binary search trees, as you can implement them. – miszcz2137 Mar 03 '20 at 16:10
  • Unfortunately, I could not find any *naturally sorted* container in the Python standard library. So I am afraid you will have to roll your own or use a third party one. You will find some references [there](https://stackoverflow.com/q/2298165/3545273) – Serge Ballesta Mar 03 '20 at 16:12

0 Answers0