Overlapping combinations with limits in Python / Ruby / PHP / Golang (Go)

Calculate the number of overlapping combination patterns with an upper limit in Python / Ruby / PHP / Golang

The number of 12 fruits taken out from 3 kinds of fruits can be calculated by the method of Duplicate combination when each fruit has 12 or more. it can. However, if there is an upper limit of 6 for each fruit, this method cannot be used. Therefore, it is necessary to realize the overlapping combination with an upper limit by another method. In this example, the dice are rolled three times, which is equivalent to the number when the total number of rolls is 12, so this formula can be used unexpectedly (I think).

Deduction principle

There is a method of calculating such overlapping combinations with an upper limit based on the deduction principle. Click here for Reference Site.

Formula

From the Reference site, set the upper limit to m, the type of fruit to n (the number of dice to shake), and the sum. If t, it can be calculated by the following formula.

\begin{eqnarray}
\sum_{ k = 0 }^{ [ \frac{ t - n }{ m } ]} (-1)^k \cdot {}_n \mathrm{ C }_k \cdot {}_n \mathrm{ H }_{ t - n - m \cdot k }
\end{eqnarray}

It becomes 25 when m = 6, n = 3, and t = 12.

Source code

Python3

import functools as ft


def permutation(n, k):
    if k > n:
        return 0
    elif 0 < k <= n:
        return ft.reduce(lambda x, y:x * y, [n - v for v in range(k)])
    else:
        return 1


def factorial(n):
    return permutation(n, n - 1)


def combination(n, k):
    return int(permutation(n, k) / factorial(k))


def homogeneous(n, k):
    return combination(n + k - 1, k)


def homogeneous_with_limit(m, n, t):
    return sum([(-1)**k * combination(n, k) * homogeneous(n, t - n - m * k) \
                for k in range(0, int((t - n) / m) + 1)])

if __name__ == '__main__':
    print(homogeneous_with_limit(6, 3, 12))

Output result


25

Ruby2.4

def permutation(n, k)
  if k > n
    0
  elsif 0 < k && k <= n then ((n - k + 1)..n).inject(:*)
  else 1
  end
end

def factorial(n)
  permutation(n, n - 1)
end

def combination(n, k)
  (permutation(n, k) / factorial(k)).to_i
end

def homogeneous(n, k)
  combination(n + k - 1, k)
end

def homogeneous_with_limit(m, n, t)
  (0..((t - n) / m)).inject(0) {|s, k| s + (-1)**k * combination(n, k) * homogeneous(n, t - n - m * k)}
end

p homogeneous_with_limit(6, 3, 12)

Output result


25

PHP7.1

<?php

function permutation(int $n, int $k) : int {
    if ($k > $n) return 0;
    elseif (0 < $k && $k <= $n)
        return array_reduce(range($n - $k + 1, $n), function ($c, $v) { return $c *= $v; }, 1);
    else return 1;
}

function factorial(int $n) : int {
    return permutation($n, $n - 1);
}

function combination(int $n, int $k) : int {
    return intval(permutation($n, $k) / factorial($k));
}

function homogeneous(int $n, int $k) : int {
    return combination($n + $k - 1, $k);
}

function homogeneous_with_limit(int $m, int $n, int $t) : int {
    return array_reduce(range(0, intval(($t - $n) / $m)), function ($s, $k) use ($m, $n, $t) {
        return $s += (-1) ** $k * combination($n, $k) * homogeneous($n, $t - $n - $m * $k);
    });
}

print(homogeneous_with_limit(6, 3, 12));

Output result


25

Golang

package main;

import (
    "fmt"
    "math"
)

func permutation(n int, k int) int {
    v := 1
    if 0 < k && k <= n {
        for i := 0; i < k; i++ {
            v *= (n - i)
        }
    } else if k > n {
        v = 0
    }
    return v
}

func factorial(n int) int {
    return permutation(n, n - 1)
}

func combination(n int, k int) int {
    return permutation(n, k) / factorial(k)
}

func homogeneous(n int, k int) int {
    return combination(n + k - 1, k)
}

func homogeneous_with_limit(m int, n int, t int) int {
    e := int((t - n) / m) + 1
    v := 0
    for i := 0; i < e; i++ {
       v += int(math.Pow(-1, float64(i))) * combination(n, i) * homogeneous(n, t - n - m *i)
    }
    return v
}

func main () {
    fmt.Printf("%v\n", homogeneous_with_limit(6, 3, 12))
}

Output result


25

Other

The deduction principle is also used in the proof of Eratosthenes Sieve. I also miss the Gaussian symbol ([x]).

There are many challenges, for example, if you roll 3 dice and the rolls are (3,5,4) and (3,4,5), you get 12, but if you don't consider this order, it's different. You need to take an approach. Also, if the maximum value of the three dice rolls is not 6 but different values, it is necessary to take another approach. The case where the order is not considered was the subject of the algorithm somewhere, but I couldn't formulate it, and I ended up turning the loop, so I would like to try again. If the maximum value is different, find the recurrence formula somewhere and it's clear.

Recommended Posts

Overlapping combinations with limits in Python / Ruby / PHP / Golang (Go)
Factorial, permutations, (duplicate) combinations in Python / Ruby / PHP / Golang (Go)
Grouping combination in Python / Ruby / PHP / Golang (Go)
Handle prime numbers in Python / Ruby / PHP / Golang (Go)
Dynamic proxy with python, ruby, PHP
Python with Go
[Scraping Summary] | Python Node.js PHP Ruby Go VBA | Scraping Yahoo! Top in 6 languages
GNU GLOBAL (gtags) + α in Go, Ruby, Python
I tried using mecab with python2.7, ruby2.3, php7
Duplicate combinations in Python
How to handle JSON in Ruby, Python, JavaScript, PHP
Scraping with selenium in Python
Working with LibreOffice in Python
Java VS PHP VS Python VS Ruby
Scraping with chromedriver in python
Debugging with pdb in Python
Working with sounds in Python
Scraping with Selenium in Python
Find permutations / combinations in Python
Zundokokiyoshi with python / ruby / Lua
Scraping with Tor in Python
About Perl, Python, PHP, Ruby
Tweet with image in Python
Combined with permutations in Python
Hello World in various languages [Python / PHP / Java / Perl / Ruby]
Morphological analysis using Igo + mecab-ipadic-neologd in Python (with Ruby bonus)
Number recognition in images with Python
Testing with random numbers in Python
Multi-stage selection (Go / C # / Ruby / Python)
Scraping with Node, Ruby and Python
GOTO in Python with Sublime Text 3
Scraping with Selenium in Python (Basic)
CSS parsing with cssutils in Python
Numer0n with items made in Python
Open UTF-8 with BOM in Python
Use rospy with virtualenv in Python3
Use Python in pyenv with NeoVim
Heatmap with Dendrogram in Python + matplotlib
Read files in parallel with Python
Password generation in texto with python
Use OpenCV with Python 3 in Window
Until dealing with python in Atom
Handling regular expressions with PHP / Python
Get started with Python in Blender
Send image with python, save with php
Working with DICOM images in Python
I tried hitting Mastodon API with Ruby (Faraday) / Python (Pycurl) / PHP (Curl)
Write documentation in Sphinx with Python Livereload
Overlapping regular expressions in Python and Java
Get additional data in LDAP with python
Spiral book in Python! Python with a spiral book! (Chapter 14 ~)
Try logging in to qiita with Python
Stress Test with Locust written in Python
Avoid nested loops in PHP and Python
Python3> in keyword> True with partial match?
Exclusive control with lock file in Python
Device monitoring with On-box Python in IOS-XE
Try working with binary data in Python
Big difference in ruby, python, httpd performance
PHP / Python / Ruby sample hitting Path API
Obtaining temporary AWS credentials in PHP, Python