0
$\begingroup$

I have a really specific problem to solve and i'm looking for an existing algorithm to help me (i hope i'm in the right section of stackExchange).

I would have to make "random" association between items but all association need to have to answer to specific conditions.

Below, an simple exemple in javascript.

  1. INPUT

    var items = [12, 32, 25, 11, 8, 2, 4, 3, 8, 9];

  2. CONDITION

All couples sum need to be between "20"(include) and "27"(include).

  1. OUTPUT

    result = [[12,9], [11,9], [25,2], ...];

This is a really "simple" exemple. I need to implement this with at least 3 or 4 items by couples but the conditions is almost the same.

Is it an algorithm that existing to easly do this kind of stuff ? Or did i need to iterate all couples possibilities to pick up randomly after ? Even a way to iterate less for the generation of all couples would be nice.

Thank you a lot for your help.

$\endgroup$
0
1
$\begingroup$

There is a similar problem, where you're looking for pairs with a given sum $S$.

For that problem, you initialize an empty set and then iterate once through your numbers. For each number $x$ you do:

  1. Check, if the number $S-x$ is in the set. If it is, you can form the pair $(x,S-x)$.

  2. Add $x$ to the set.

If its allowed to use a number twice, you would only have to switch step (1) and (2).

To check for ranges instead of exact sums you would have to adapt your data structure. You would exchange the set with a range tree and do the following:

  1. Query your range tree for the range $(low-x,high-x)$ (where low and high are 20 and 27 in your example). This query will return a set $P$ of numbers and you can form a pair $(x,p) \forall p \in P$.

  2. Add $x$ to the range tree.

Obviously, this approach only works for pairs. If you want to get all tuples with 4 elements you could first generate all distinct pairs and then try to combine them with the approach I've outlined above. This would result in an $\mathcal O (n^2 \log n)^*$ algorithm (same for tuples with 3 elements, though you would add the pair-sums to the DS and query with the elements from your initial array and not with other pair-sums).

*: This runtime is only correct if the size of tuples in a range is bounded with $\mathcal O(1)$. The worst case without this assumption is of course $\mathcal (N^4)$, when e.g. you have $N$ positive numbers and your allowed range is from $0$ to $\infty$ (result = all possible 4-tuples, without constraints).

PS: I think it's highly likely, that there cannot be a better algorithm, as this problem is an adaptation of 3SUM.

$\endgroup$
3
  • $\begingroup$ Interesting algorithm. Seems to assume the ordering of the output pairs don't matter. Suppose the first half of the stream is all 3 and next half is all 4 ... The worst case is no pair can be formed for first half of the stream. $\endgroup$ – R zu Oct 7 '18 at 1:17
  • $\begingroup$ Yeah, those pairs where 3 occurs will be found later. $\endgroup$ – oerpli Oct 7 '18 at 8:40
  • $\begingroup$ Is it correct to say that its possible too to try to make couples of 4 like that : 1. Make step 1 and 2 with S/2 2. Make step 1 and 2 with previous generate couple sum with S (With adaptive to range three). Maybe that will be more fast than than the solution of R zu ? $\endgroup$ – OOM Oct 8 '18 at 12:57
0
$\begingroup$

Assume the input is static (not a stream).

Assume needs to make lots of random pairs satisfying the condition.

Let's say the constraint is 4 $\le$ sum of the pairs $\le$ 10.

Setp 1. Sort the items.

data array: [1, 3, 4, 5, 7, 9]

Step 2. For each item, precompute the ranges that satisfies the condition.

As element 1, and the next element (offset 1) can form a pair.
    offset array: [1, ... ] 
As element 1 can form valid pairs with 3, 4, 5, 7, 9, which are 
5 elements
    size array:   [5, ... ]  
1 and 5 are offset and size of the 0th range.

Step 3. Randomly select a range, weighted by the sizes of the ranges. This can be done by selecting a random number x between 1 (inclusive) and the sum of sizes of all range (inclusive). Then search for x in the cumulative sum of the size array by binary search.

 If size array is:  [5, 1,  4,  6,  7]
 cumulative sum is: [5, 6, 10, 16, 23]

Step 4. If the ith range is selected, one of the element of the pair is data[i].

Step 5. Randomly select an element within the selected range. Let's say the jth element is selected. The other element of the pair is data[i + j + offset[i]].

Step 6. If you want the larger element in a pair can be either the 0th or 1st element of the pair, then you can randomly swap the two elements of the pair.

$\endgroup$
5
  • $\begingroup$ I just make this up. Probably there are much faster ways. $\endgroup$ – R zu Oct 7 '18 at 1:08
  • $\begingroup$ Please accept an answer. I am broke after starting a bounty on a question... $\endgroup$ – R zu Oct 7 '18 at 15:02
  • $\begingroup$ With this algorithm i will cant have by exemple : 1. Input => [1, 3, 4, 5, 7, 9] 2. One random [1, 4, 9] (for sum between 10 and 15) Because 4 and 9 are separate by 5 and 7 is that ? (if im understanding good) $\endgroup$ – OOM Oct 8 '18 at 13:02
  • $\begingroup$ Well. For element 1, the range is just [9]. So all pairs containing 1 must be either (1, 9) and (9, 1). Without step 6, the algorithm gives (1, 9) when it choose element 1 in step 3. The pair (1, 4) have a sum of 5, which does not satisfy your condition. $\endgroup$ – R zu Oct 8 '18 at 15:10
  • $\begingroup$ The $i^{th}$ range does not contain any element in the data array with an index less than $i$. $\endgroup$ – R zu Oct 8 '18 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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