Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much
 
PerlMonks  

Re^3: Faster alternative to Math::Combinatorics

by Anonymous Monk
on Sep 01, 2017 at 16:55 UTC ( [id://1198535]=note: print w/replies, xml ) Need Help??


in reply to Re^2: Faster alternative to Math::Combinatorics
in thread Faster alternative to Math::Combinatorics

I'm only looking for unordered tuples
The mathematical terminology is kind of backwards from the computer science terminology here. You mean that the order of the tuple doesn't matter, and you've put your examples in numerically ascending sequence for neatness. A programmer looks at that and says, "those tuples are ordered."

Replies are listed 'Best First'.
Re^4: Faster alternative to Math::Combinatorics
by AppleFritter (Vicar) on Sep 01, 2017 at 17:01 UTC

    I know, it's a bit confusing. That's why I wrote:

    I'm trying to generate all multisets (bags) of a specific total "weight" (let's call it w), where each element comes from a given list (of numbers, in this case), and each list element may have multiplicity 0..w in each multiset.

    and:

    The order in which the multisets itself are generated isn't important to me either, BTW. I've only listed them in order for the sake of readability.

    I'm sure there's standard terms for these, too, terms that I simply don't know.

      If I understand you well, I think a selection of items from a set where the selection order is irrelevant is called a combination. See https://en.wikipedia.org/wiki/Combination. Note that combinations can be with or without repetitions.

      Perhaps using this term might help you searching the Internet for algorithms.

        Ah, yes, thanks. Wikipedia writes:

        A k-combination with repetitions, or k-multicombination, or multisubset of size k from a set S is given by a sequence of k not necessarily distinct elements of S, where order is not taken into account: two sequences of which one can be obtained from the other by permuting the terms define the same multiset. In other words, the number of ways to sample k elements from a set of n elements allowing for duplicates (i.e., with replacement) but disregarding different orderings (e.g. {2,1,2} = {1,2,2}).

        So it seems that they're called "multicombinations" or "multisubsets", and I wasn't too far off the mark when talking about multisets.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://1198535]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (4)
As of 2024-03-29 13:25 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found