algorithm - Enumerating unique k-combinations from a multiset with known repetitions (finite multiplicities)

Question

I'll start with a mental exercise I made up to make what I'm trying to do easier to explain and less obscure.

---

Say I know of a shop called FRUITS which has infinite quantities of every fruit currently known ¹.

Say that I got a machine that uses complex combinatorial logic to convert any set of M=4 items from FRUITS to an object not among the 4 I gave ². I can test the type of output I would get by giving it 4 names as well without using up the fruits.

I ask a friend to go into FRUITS, pick a total number of fruits >= M (with at least 2 types), and they'll give me the name and count for each fruit they chose (e.g. {Apple: 1, Banana: 3, ... } or [Apple,Banana,...] and [1,3,...]).

---

I want to create an efficient algorithm (any language can be used to illustrate) to find all unique inputs I could give my machine without needing to check all M-combinations or to list out every single fruit (viz. in lexicographic order) using the pair of lists ³. I want to do this without recursion, as the lists could be fairly large ⁴.

---

The function I currently have takes names as one list, and counts as another of the same length (say N)⁵. I'm hoping to have the final version output a list of m lists with their lengths being equal to the number of unique combinations (m =4 in my earlier analogy); these lists will hold indices to the names/counts lists (pseudocode to illustrate -- note the below return value 1-indexed):

function (names: [A,B,C], counts: [2,2,1], m = 4) {
   // ...
   return [
      [1,1,1],[1,2,1],[2,2,2],[2,3,3]
   ]
   // Transposed matrix form to clearly show the 3 combinations (substituted names for indices)
   //
   //   A A B B
   //   A B B C
   //   A A B C
}
    

(The reason I chose to return m lists is because m has a fair chance of being a constant later on)

This is actually part of a larger project I want to do involving combinatorial optimization -- i.e. the real goal would be to find the combinations needed to maximize/minimize the sum of a quantitative property shared by the items in the list (e.g. maximize Vitamin C). But I felt like that question by itself would be too broad or difficult, so I'm starting with off what I think is the first step.

---

^{1 In this world, all fruits with the same name as exactly identical (e.g. any Apple is equivalent to another Apple).
2 For simplicity, you can assume the output is not in FRUITS.
3 Bonus points if a callback or block of code can be effectively integrated as combinations are found (e.g. to test with my fruit converter and create a map).
4 I've actually have a recursive version working, but I'm hoping for a more efficient algorithm as it looks like I'll be working in Lua
5 Sanity checks aren't important here as input will be checked beforehand}

Answer 1

等待大神答复