Что partition делает в этой функции?

#python

Вопрос:

Я наткнулся на этот вопрос, спрашивающий, что будет выполнять функция ‘foo’. Однако я не мог понять, что делает «раздел» в этой функции? Другой информации не предоставлено. Я знаю о разделе с точки зрения манипулирования строками, но здесь он действует в списке.

 def foo(nums, k):
    pos = partition(nums, 0, len(nums)-1)
    if k > pos 1:
        return foo(nums[pos 1:], k-pos-1)
    elif k < pos 1:
        return foo(nums[:pos], k)
    else:
        return nums[pos]

1. Какие еще исследования вы провели? Кроме того, пожалуйста, удалите изображение и вставьте правильно отформатированный код.

2. Не могли бы вы предоставить информацию об импортированных модулях? Единственный раздел, который я знаю в стандартной библиотеке, — это str.partition , но это не тот случай.

3. Все, что он сделает, это вызовет NameError , потому что оно не определено.

4. «раздел» может означать разделение на 3 вещи: [значения ниже, значение раздела, значения выше]. И это, похоже, имеет место здесь. Разделите и верните тот, который содержит k.

Ответ №1:

Это зависит от определения partition . Однако, foo скорее всего, пытается найти k -й наименьший элемент в nums .

Функция partition, которую я имею в виду, разбивает список пополам и возвращает среднюю точку. В зависимости от k , foo функция решает, использовать ли левый или правый подмассив, а затем соответствующим образом корректирует значение k .

Вот развернутый пример, включающий некоторые закомментированные строки отладки, которые вы можете включить. Я использовал реализацию partition() из Введения в алгоритмы Кормена и др.

 import random

def partition(A, p, r):
  """ This uses 1-based indexing.   """
  #print(f"    partition: {A} {p} {r}")

  x = A[r-1]
  i = p - 1
  for j in range(p, r):
    if A[j-1] <= x:
      i = i   1
      (A[i-1], A[j-1]) = (A[j-1], A[i-1])
  (A[i], A[r-1]) = (A[r-1], A[i])
  return i   1
  
def partition2(A, p, r):
  """ Zero-based indexing version """
  return partition(A, p 1, r 1) - 1
  
def foo(nums, k):
  #print(f"    foo: {nums} {k}")
  pos = partition2(nums, 0, len(nums) - 1) 
  #print(f"      pos: {pos}")
  if k > pos   1:
    return foo(nums[pos 1:], k-pos-1)
  if k < pos   1:
    return foo(nums[:pos], k)
  else:
    return nums[pos]
  
# generate some random samples
random.seed(0)
for sample in range(5):
    # random value [1, 5]
    k = random.randint(1, 5)
    # list of 5 random values in range [0, 20]
    l = [ random.randint(0, 20) for i in range(6) ]
    # result of foo
    res = foo(l, k)
    # inform
    print(f"For list {l} and k = {k}, we got {res}")

Вот результаты запуска этой программы:

   For list [1, 8, 12, 16, 15, 13] and k = 4, we got 13
  For list [4, 11, 18, 6, 16, 15] and k = 3, we got 11
  For list [4, 3, 19, 8, 17, 19] and k = 3, we got 8
  For list [9, 3, 2, 10, 15, 17] and k = 2, we got 3
  For list [6, 13, 10, 19, 20, 11] and k = 1, we got 6