How can I randomly find a combination from an array with duplicate elements and it's sum equal n.
Example
arrayis[1, 2, 2, 3]andnis3- answers are
1 2,1 2,3 - If
randomSubsetSum(array, n)is solution, thenrandomSubsetSum([1,2,2,3], 3)will return one of1 2,1 2,3. Note:1 2appear twice as often as3 - A real-world scenario: random selection of questions from a question bank for an exam
I found some similar questions and solutions:
Q: Finding all possible combinations of numbers to reach a given sum
A: solution A and solution B
Q: Rank and unrank integer partition with k parts
A: solution C
Defect
solution A and solution B can not random find combination. solution C does not allow duplicate elements.
My Java solution
public List<Integer> randomSubsetSum(List<Integer> list, Integer n) {
list.removeIf(e -> e > n);
int maxSum = list.stream().reduce(0, Integer::sum);
if (maxSum < n) {
throw new RuntimeException("maxSum of list lower than n!");
}
if (maxSum == n) {
return list;
}
final SecureRandom random = new SecureRandom();
// maybe helpful, not important
final Map<Integer, List<Integer>> map = list.stream().collect(Collectors.groupingBy(Function.identity()));
final List<Integer> keys = new ArrayList<>(map.keySet());
final List<Integer> answers = new ArrayList<>();
int sum = 0;
while (true) {
int keyIndex = random.nextInt(keys.size());
Integer key = keys.get(keyIndex);
sum = key;
// sum equal n
if (sum == n) {
List<Integer> elements = map.get(key);
answers.add(elements.get(random.nextInt(elements.size())));
break;
}
// sum below n
if (sum < n) {
List<Integer> elements = map.get(key);
answers.add(elements.remove(random.nextInt(elements.size())));
if (elements.isEmpty()) {
map.remove(key);
keys.remove(keyIndex);
}
continue;
}
// sum over n: exists (below = n - sum key) in keys
int below = n - sum key;
if (CollectionUtils.isNotEmpty(map.get(below))) {
List<Integer> elements = map.get(below);
answers.add(elements.get(random.nextInt(elements.size())));
break;
}
// sum over n: exists (over = sum - n) in answers
int over = sum - n;
int answerIndex =
IntStream.range(0, answers.size())
.filter(index -> answers.get(index) == over)
.findFirst().orElse(-1);
if (answerIndex != -1) {
List<Integer> elements = map.get(key);
answers.set(answerIndex, elements.get(random.nextInt(elements.size())));
break;
}
// Point A. BUG: may occur infinite loop
// sum over n: rollback sum
sum -= key;
// sum over n: remove min element in answer
Integer minIndex =
IntStream.range(0, answers.size())
.boxed()
.min(Comparator.comparing(answers::get))
// never occurred
.orElseThrow(RuntimeException::new);
Integer element = answers.remove((int) minIndex);
sum -= element;
if (keys.contains(element)) {
map.get(element).add(element);
} else {
keys.add(element);
map.put(element, new ArrayList<>(Collections.singleton(element)));
}
}
return answers;
}
At Point A, infinite loop may occur(eg. randomSubsetSum([3,4,8],13)) or use a lot of time. How to fix this bug or is there any other solution?
CodePudding user response：
If I get it right, the core task is to filter the subset having a specific sum and return a random one. Since the task is not to come up with an algorithm on how to build all susets of a given list, I would suggest to use a librarry which does that task for you. One of such a library is combinatoricslib3. If you happen to already use Apache Commons or Guava, they also have some methods implemented to get all subsets of a list.
Using combinatoricslib3 getting the subsets is as simple as:
Generator.subset(List.of(1, 2, 2, 3))
.simple()
.stream()
.forEach(System.out::println);
to get:
[]
[1]
[2]
[1, 2]
[2]
[1, 2]
[2, 2]
[1, 2, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]
[2, 3]
[1, 2, 3]
[2, 2, 3]
[1, 2, 2, 3]
For your task described above, the following could be a starting point using the lib mentioned to outsource the finding of subsets:
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;
import org.paukov.combinatorics3.Generator;
public class TestJavaClass {
public static void main(String[] args) {
System.out.println(randomSubsetSum(List.of(1, 2, 2, 3), 3));
}
public static List<Integer> randomSubsetSum(List<Integer> list, Integer n) {
List<List<Integer>> subLists = Generator.subset(list)
.simple()
.stream()
.filter(x -> !x.isEmpty())
.filter(x -> sum(x).equals(n))
.collect(Collectors.toList());
if (!subLists.isEmpty()){
return subLists.get(new Random().nextInt(subLists.size()));
}
else {
throw new IllegalArgumentException("No subset found in: " list " having a sum = " n);
}
}
public static Integer sum(List<Integer> list) {
return list.stream().reduce(0, Integer::sum);
}
}
For simplicity I've removed the handling of the edge cases. Add it if needed:
list.removeIf(e -> e > n);
int maxSum = list.stream().reduce(0, Integer::sum);
if (maxSum < n) {
throw new RuntimeException("maxSum of list lower than n!");
}
if (maxSum == n) {
return list;
}
CodePudding user response：
Here is a solution lightly adapted from solution A.
from random import random
def random_subset_sum(array, target):
sign = 1
array = sorted(array)
if target < 0:
array = reversed(array)
sign = -1
# Checkpoint A
last_index = {0: [[-1,1]]}
for i in range(len(array)):
for s in list(last_index.keys()):
new_s = s array[i]
total = 0
for index, count in last_index[s]:
total = count
if 0 < (new_s - target) * sign:
pass # Cannot lead to target
elif new_s in last_index:
last_index[new_s].append([i,total])
else:
last_index[new_s] = [[i, total]]
# Checkpoint B
answer_indexes = []
last_choice = len(array)
while -1 < last_choice:
choice = None
total = 0
for i, count in last_index[target]:
if last_choice <= i:
break
total = count
if random() <= count / total:
choice = i
target -= array[choice]
last_choice = choice
if -1 < choice:
answer_indexes.append(choice)
return [array[i] for i in reversed(answer_indexes)]