Is it possible to model this die with anydice?

Question

In anydice, I'd like to create a die, so that a roll would be the sum of 4 random values from the following sequence:

{1, 1, 1, 1, 1, 3, 3, 3, 5, 5, 7}

So that each number in the sequence is used at maximum once. (That is 3+5+5+7 result is possible where as 5+5+7+7 is not because there are not enough 7s for that) Is this possible?

This is a cards mechanics, not dice mechanics. I'm trying to get a roll by getting a player to draw several card out of pool of cards that I put together. While Anydice is mostly for dice mechanics not for cards drawing mechanics Anydice works well for probability analysis in general, and for sharing the visual spread of probabilities with less technically apt people.

Answer 1

I came up with two solutions, which while inherently different, give the same result. This instils confidence in me that they are correct.

Solution 1

This solution is the one I started working on before I read Sandwich's answer. You can try it here. The idea is to use Buckles algorithm for mapping an lexicographical index (from a die roll) to a selection from my sequence. Let's look at the code:

set "maximum function depth" to 100
function: factorial A:n {
  RESULT: 1
  loop N over {1..A} { RESULT: RESULT*N }
  result: RESULT
}
function: N:n choose K:n {
  result: [factorial N]/[factorial K]/[factorial N-K]
}
function: buckles inner CURRENT:n N:n K:n LIMIT:n INDEX:n {
  NEWLIMIT: [N-CURRENT choose K] + LIMIT
  if NEWLIMIT >= INDEX { result: {CURRENT,LIMIT}}
  else { result: [buckles inner CURRENT+1 N K NEWLIMIT INDEX]}
}
function: N:n buckles K:n index INDEX:n {
  RESULT: {}
  CURRENT: 0
  LIMIT: 0
  loop I over {1..K-1}{
    TUPLE: [buckles inner CURRENT+1 N K-I LIMIT INDEX]
    CURRENT: 1@TUPLE
    LIMIT: 2@TUPLE
    RESULT:{RESULT,CURRENT}
  }
  result: {RESULT,CURRENT+INDEX-LIMIT} 
}
function: select SELECTOR:s from SEQUENCE:s {
  RESULT: {}
  loop I over SELECTOR { RESULT: {RESULT,I@SEQUENCE} }

  result: RESULT

}
function: draw K:n items from SEQUENCE:s at lexicographical index INDEX:n {
  result: [select [#SEQUENCE buckles K index INDEX] from SEQUENCE]
}
function: draw from SEQUENCE:s K:n times {
  INDEX: d[#SEQUENCE choose K]
  result: [draw K items from SEQUENCE at lexicographical index INDEX]
}
SEQUENCE: {1, 1, 1, 1, 1, 3, 3, 3, 5, 5, 7}
output [draw from SEQUENCE 4 times] named "mydie"

The factorial and choose functions are self explanatory. The first calculates 123....*n, and the second one gives the total number of different ways to get k item out of n, in my case 4 out of 11. buckles and buckles inner implement the Buckles algorithm itself. If we pass N=11, P=4 and X=1 to the buckles function we will receive {1,2,3,4}. If we pass N=11, P=4 and X=2, we will receive {1,2,3,5} and so on an so forth until we go all the way to N=11, P=4 and X=330 to get {8,9,10,11}. Note that 330 here is [11 choose 4].

select is a helper function, that takes a selector, a sequence and returns the resulting sequence. For example for selector {1,6,7,11} and sequence {1, 1, 1, 1, 1, 3, 3, 3, 5, 5, 7} the result will be {1,3,3,7}.

draw items function selects K items from the given sequence at a given lexicographical index. For example with K = 4 at index 1 and sequence {1, 3, 5 , 9, 11} the result will be {1, 3 , 5 , 9}.

The second draw function allow you specifying a sequence and the number of items to draw from it. That will be the die.

Solution 2

This one is completely inspired by sandwich's answer. You try it here. And here is the code:

function: remove N:n from SEQUENCE:s {
  RESULT:{}
  REMOVED: 0
  loop C over SEQUENCE {
    if (REMOVED = 0) & (C=N) { REMOVED: 1 } else { RESULT: {RESULT,C} }
  }
  result: RESULT
}
function: draw from SEQUENCE:s with X:n and RESULT:s C:n more times{
  if C = 0 {
   result: RESULT
  } else {
    SEQUENCE: [remove X from SEQUENCE]
    result: [draw from SEQUENCE with dSEQUENCE and {RESULT,X} C-1 more times]
  }
}
function: draw from SEQUENCE:s N:n times {
  result: [draw from SEQUENCE with dSEQUENCE and {} N more times]
}
SEQUENCE:{1, 1, 1, 1, 1, 3, 3, 3, 5, 5, 7}
output [draw from SEQUENCE 4 times] named "mydie"

I was not sure how to remove a value from an existing sequence, so I had to write my own function for that. It's remove. The two draw functions implement sandwich's idea of rolling a die and then removing the result from the die sequence. There are two of them, because one of them is recursive and the other bootstraps the first one.

I can tell you that the first solution took me about 3 hours, and the second one only a few minutes. Well done sandwich!

Answer 2

To create the die you're looking for, you can use the following syntax:

output d{1, 1, 1, 1, 1, 3, 3, 3, 5, 5, 7} named "1d11"

That would roll a single die named d11 that has an equal probability of rolling each of the individual results in the sequence.

The way you'd likely have to remove each individual step from the dice is you'd have to use the die result to define a variable, and if that variable equals seven, to roll another die with the seven in the sequence removed. Each step of the "if/else" statement would define a new variable (w/x/y/z).

If that seems like too much work you can just roll the one die to get the results you're trying to achieve, however, rerolling when you roll a 7 once, a 5 twice, or a 3 thrice.

Answer 3

Icepool

My Icepool Python package has some direct support for decks:

from icepool import Deck
deck = Deck([1, 1, 1, 1, 1, 3, 3, 3, 5, 5, 7])
output(deck.deal(4).sum())

You can run this in your browser here.

Algorithm notes

Drawing without replacement (cards) is not the same as drawing with replacement (dice pools), but they are quite similar -- where dice pools follow the multinomial distribution, cards follow the multivariate hypergeometric distribution.

AnyDice's primary algorithm is to enumerate all possible sorted sequences that could come out of a roll of a dice pool, which is considerably less than the number of ordered sequences. In principle it would be possible for AnyDice to be extended to apply this same strategy to dealing from decks. In this case there are only \$\binom{11}{4} = 330\$ possible deals even before accounting for duplicate cards, so this would be easily computed.

However, decks are more likely to run into computational problems with this algorithm:

• Rolling 10d10, which is on the larger side of dice pools, only results in \$\binom{19}{10}\$ or less than 100 thousand possible sorted sequences, which is quite manageable.
• AnyDice's 5-second limit expires at around 10d18 when using highest. That's \$\binom{27}{10}\$ or less than 10 million possible sequences. Dice pool problems of this size are not common, though not unheard-of either, especially when multiple pools are involved; see e.g. Neon City Overdrive and Infinity the Game.
• In contrast, a deck could easily have 50 unique cards; dealing 10 of those has \$\binom{50}{10}\$ or more than 10 billion possible sorted sequences. At the above rate it would take more than an hour.

It is possible to go considerably faster. The numerators of both types of distributions can be decomposed into a product of binomials, each binomial representing how many of a particular card/face were drawn. In many cases, this allows the use of more efficient algorithms that do not explicitly enumerate all possible sorted sequences. For example, suppose we deal 10 cards from a deck numbered 0 to 49. Icepool can evaluate the length of the longest straight in mere milliseconds:

from icepool import Deck
deck = Deck(range(50))
output(deck.deal(10).largest_straight())