1
$\begingroup$

Initial collection A = [1,2,3] should provide such combinations:

{(1, 2), (1, 3), (2, 3)}

I want to pop the first combination (1, 2), so after this I can pop only from {(1, 3), (2, 3)}

Collection A can grow in size. How example:

A = [1,2,3] : {(1, 2), (1, 3), (2, 3)}
pop (1, 2) from A combinations -> A = [1,2,3] : {(1, 3), (2, 3)}
add 4 to A -> A = [1,2,3,4] : {(1, 3),(2, 3),(1, 4),(2, 4),(3, 4)}

I'm looking for the efficient data structure/algorithm to implement such behaviour. I'll be satisfied with both: single combination pop or iteration of all currently existing combinations. Elements can be unordered, but behaviour like heap would be better. So combination with the greater sum would be ready to be peeked first.

Also there is one optional addition. I want to combine not all elements, but only those which can be combined. In case with numbers, only elements with the same absolute value can be combined. Like A = [-1,1,2,3] : {(-1, 1)}. For other type of objects there is a special compare function ofc. And any object can generate all objects it can combined with.

$\endgroup$
2
  • $\begingroup$ Just to clarify, you want a data structure that can store a collection such that you can add a new element, pop a pair out of the stoted elements, and iterate all remaining pairs? What do you mean by heap-like behavior? Can you elaborate your additional requirement? $\endgroup$
    – Russel
    Apr 3, 2022 at 12:27
  • $\begingroup$ @Russel, 1) I'd be happy with just add / pop. Iteration is just option instead of pop, if it would be impossible to implement single element peek. 2) About heap - like: I mean priority of elements. Max element should be peeked first. But this is optional feature. $\endgroup$ Apr 3, 2022 at 12:37

2 Answers 2

2
$\begingroup$

I think you can achieve your minimum requirement by augmenting a doubly-linked list.

Augmentation

  • For each node, in addition to the $next$ and $previous$ pointer, add a new pointer $pair$. Initially, for a node $n$, $n.pair = n.next$.
  • Add an $element$ field that will hold the added element to the collection.
  • Add a boolean field $completed$ to each node, which is initially set to false.
  • In addition to the $head$ pointer, add a new pointer $cur$ that initially points to the first node.

Pop

  1. If $cur$ points to the last node, then there are no more elements to pop return $null$.
  2. Otherwise, if $cur.completed$ is true set $cur.pair$ to $cur.pair.next$ and $cur.completed$ to false.
  3. Create $p = (cur.element, cur.pair.element)$.
  4. If $cur.pair$ is not the last node, set $cur.pair = cur.pair.next$.
  5. Else, set $cur.completed$ to true and let $cur = cur.next$.
  6. Return $p$.

Add

  1. Create a new node containing the added element and add this node to the end of the linked list, updating the $next$ and $pair$ pointer of the previous last node accordingly.
  2. Set $cur$ to the first node.

Analysis

All operations take $O(1)$ time.

You can easily implement iteration with this implementation, which I will leave for you to think about. In case you want to pop a pair based on the order of the elements, maybe you can augment a BST, but I have not considered this much, but updating the $pair$ pointer will be a little tricky, I think.

$\endgroup$
2
$\begingroup$

The data structure stores the last value generated $(i,j)$. In order to generate the next value, iterate over all $i < k < j$ (where comparison here refers to the order they appear in $A$) until you find some $k$ which is compatible with $j$. If there is none, advance $j$ to $j'$, and find the first $i' < j'$ which is compatible with $j'$, if any. If there is none, advance $j'$ again, and try again, and so on, until you run out of elements, in which case you can announce that there is no next value.

Initially, there is no last value generated, so you need a special subroutine to find the first value. This subroutine is really contained in the code for next described in the previous paragraph: go over all $j$ in order, and for each, attempt to find a compatible $i < j$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.