Как найти пары в массиве питон

Есть список чисел в датафрейме. Из этого списка нужно найти пары чисел a и b, такие чтобы a == -b. Если такие пары есть их нужно дропнуть.

Вопрос собственно в том, как это сделать максимально эффективно?

Условия

• a == -b
• Необходимо найти и удалить все пары.
• Числа удаляются только папарно.
• Числа корорые уже входят в пару не могут быть частью другой пары. Т.е. для числа с нужно искать другое d даже если с == -b или с == -a
• Все равно что происходит с нулями 0 == -0. Можно удалить или оставить, главное чтобы работало быстрее.
• Не обязательно, но было бы лучше, если бы растояние по индексу, между парой, было минимальным.
• Порядок чисел не должен поменятся после удаления. Нужно оставить исходные индексы датафрейма.

Текущая реализация

def drop_paired(data:pd.DataFrame, target_column:str):
    result = data.copy()
    result['index'] = result.index
    # Сортируем значения без учета знака
    result = result.sort_values([target_column, 'index'], key=abs)
    result['drop'] = False

    value_a = index_a = np.nan
    i = start_i = 0
    while i < len(result):
        row = result.iloc[i]
        
        # Проверяем не использовано это число в качестве какой либо пары
        if(~row['drop']):
            # Если значение и индекс первого числа в паре (a) не определены, задаем новые
            if(index_a is np.nan):
                value_a = row[target_column]
                index_a = row['index']
                start_i = i

            # Если нашли b == -a, ставим пометку на удаление и опустошаем значение и индекс первого числа в паре
            elif(row[target_column] == -value_a):
                result.loc[row['index'], 'drop'] = True
                result.loc[index_a, 'drop'] = True
                value_a = index_a = np.nan
                
                # Возвращаемся назад для поисков другой пары среди этих же значений
                i = start_i
                continue

            # Если есть а с более "старшим" индексом, возьмём его, чтобы расстояние между a и b было минимальным
            elif(row[target_column] == value_a):
                index_a = row['index']

            # Если числа не равны по модулю, задаем новые
            else:
                value_a = row[target_column]
                index_a = row['index']
                start_i = i
        
        i += 1
            
    result = result[~result['drop']].sort_index()   
    return result[list(data)]

Результат работы

np.random.seed(0)
df = pd.DataFrame(np.random.randint(-6, 11, 20))

print("До дропа")
display(df.value_counts())
display(df)
print("n--------------nПосле дропа")
display(drop_paired(df, 0).value_counts())
drop_paired(df, 0)

Итого

Алгоритм работает, но меня смущает гавнокодовость данного решения. Как сделать лучше?

Sometimes, while working with Python list, we can have a problem in which we need to extract all the possible pairs that can be performed from integers from list. This kind of problem can occur in many domains such as day-day programming and web development. Let’s discuss certain ways in which this task can be performed.

Input : test_list = [1, 7, 4] 
Output : [(1, 7), (1, 4), (7, 4)] 

Input : test_list = [7, 4] 
Output : [(7, 4)]

Method #1 : Using list comprehension + enumerate() This is one of the ways in which this task can be performed. In this, we perform the task of pairing using nested loops in list comprehension recipe, and enumerate() is used to check with the next indices while iteration. 

The original list : [1, 7, 4, 3]
All possible pairs : [(1, 7), (1, 4), (1, 3), (7, 4), (7, 3), (4, 3)]

Time complexity: O(n^2), where n is the length of the input list.
Auxiliary space: O(n^2), due to the list comprehension creating a new list of all possible pairs.

Method #2: Using combinations() This is one of the ways in which this task can be performed. In this, we just using inbuilt function for pairing and sending 2 as value for making pairs of size 2. 

The original list : [1, 7, 4, 3]
All possible pairs : [(1, 7), (1, 4), (1, 3), (7, 4), (7, 3), (4, 3)]

Time Complexity: O(n^2) .
Auxiliary Space: O(n^2).

Method #3: Using nested loops

In this approach, we can use nested loops to iterate through each element in the list and form pairs. We can then append each pair to a new list and return it as the result.

step-by-step approach

1. Define a list called test_list containing some integer values.
2. Print the original list using the print() function.
3. Create an empty list called res. This list will hold all the possible pairs.
4. Determine the length of the test_list using the len() function and store it in a variable called n.
5. Use a nested loop structure to generate all the possible pairs of elements in the test_list. The outer loop will iterate over the elements in the list starting from the first element, and the inner loop will iterate over the remaining elements in the list starting from the next element.
6. In each iteration of the loop, append a tuple containing the current pair of elements to the res list.
7. Print the result list using the print() function.
8. I hope this helps!

The original list : [1, 7, 4, 3]
All possible pairs : [(1, 7), (1, 4), (1, 3), (7, 4), (7, 3), (4, 3)]

Time complexity: O(n^2), where n is the length of the list.

Auxiliary space: O(n^2), as we need to store all possible pairs in the result list.

METHOD 4:Using recursion

APPROACH:

The program finds all possible pairs of elements in a given list and returns the pairs as a list

ALGORITHM:

1. Define a function called “all_pairs” that takes a list as input.
2. If the length of the list is less than or equal to 1, return an empty list.
3. Create an empty list called “pairs”.
4. For each element in the list, except the first element, create a tuple of that element and the first element.
5. Append the tuple to the “pairs” list.
6. Recursively call the “all_pairs” function with the list starting from the second element.
7. Return the concatenation of the “pairs” list and the result of the recursive call to “all_pairs” function.

All possible pairs: [(1, 7), (1, 4), (1, 3), (7, 4), (7, 3), (4, 3)]

Time Complexity:
The time complexity of this algorithm is O(n^2), where n is the length of the input list. This is because for each element in the list, the algorithm has to create a tuple with every other element in the list except itself.

Space Complexity:
The space complexity of this algorithm is O(n^2), where n is the length of the input list. This is because the algorithm creates a list of tuples, each containing two elements, for every pair of elements in the input list.

METHOD 5:Using re module.

APPROACH:

This program uses the re module to extract integers from the given input string, and then generates all possible pairs of those integers using a list comprehension. The pairs are then printed as output.

ALGORITHM:

1.Import the re module.
2.Define the input string.
3.Use re.findall() function to extract all integers from the input string and convert them to a list of integers using a list comprehension.
4.Use nested loops to generate all possible pairs of integers from the list.
5.Store the pairs in a list.
6.Print the list of pairs.

All possible pairs: [(1, 7), (1, 4), (1, 3), (7, 4), (7, 3), (4, 3)]

Time complexity: O(n^2)
Auxiliary Space: O(n)

Last Updated :
18 May, 2023

Like Article

Save Article

Дан несортированный массив целых чисел, найти в нем пару с заданной суммой.

Например,

Потренируйтесь в этой проблеме

Существует несколько методов решения этой проблемы с использованием грубой силы, сортировки и хеширования. Они обсуждаются ниже:

1. Использование грубой силы

Наивное решение состоит в том, чтобы рассматривать каждую пару в заданном массиве и возвращаться, если искомая сумма найдена. Этот подход демонстрируется ниже на C, Java и Python:

Временная сложность приведенного выше решения равна O(n²) и не требует дополнительного места, где n это размер ввода.

2. Использование сортировки

Идея состоит в том, чтобы отсортировать заданный массив в порядке возрастания и поддерживать пространство поиска, сохраняя два индекса (low а также high), который изначально указывает на две конечные точки массива. Затем уменьшите область поиска nums[low…high] на каждой итерации цикла путем сравнения суммы элементов, присутствующих в индексах low а также high с желаемой суммой. Увеличение low если сумма меньше ожидаемой суммы; в противном случае уменьшить high если сумма больше желаемой суммы. Если пара найдена, вернуть ее.

Ниже приведена реализация C++, Java и Python, основанная на идее:

Временная сложность приведенного выше решения равна O(n.log(n)) и не требует дополнительного места.

3. Использование хеширования

Мы можем использовать хеш-таблица решить эту задачу за линейное время. Идея состоит в том, чтобы вставить каждый элемент массива nums[i] в карту. Мы также проверяем, есть ли разница (nums[i], target - nums[i]) уже есть на карте или нет. Если разница видна раньше, напечатайте пару и вернитесь. Алгоритм может быть реализован следующим образом на C++, Java и Python:

Временная сложность приведенного выше решения равна O(n) и требует O(n) дополнительное пространство, где n это размер ввода.

 
Упражнение: Расширьте решение, чтобы вывести все пары в массиве, имеющие заданную сумму.

 
Похожие сообщения:

Найти тройку с заданной суммой в массиве

4–Суммированная задача | Четверки с заданной суммой

Найдите пару с заданной суммой в BST

Покажите свой код.
Требуется найти разбиение с наибольшим количеством пар?
Дело в том, что разные разбиения дают разное кол-во пар.
Например, у массива [1, 2, 3, 4] существует два разбиения: {(2, 3)} и {(1, 2), (3, 4)}.
Вот пример решения (сложность O(N*log N)):

def pairs(src):
    i = 0
    src.sort()
    result = list()    
    while i + 1 < len(src):
        if src[i+1] - src[i] == 1:
            result.append((src[i], src[i+1]))
            src = src[:i] + src[i+2:]
            i = max(0, i-1)
        else:
            i += 1
    return result

src1 = [1, 5, 9, 11, 10, 4]
src2 = []
src3 = [1, 5, 2, 9, 1, 1, 4, 2, 2, 2]
print(src1, pairs(src1))
print(src2, pairs(src2))
print(src3, pairs(src3))

ps. Обращаю внимание, что функция меняет список!