README

Twiddle

A library for generating k-combinations.

This provides a PHP implementation of Phillip J Chase’s TWIDDLE, `Algorithm 382: Combinations of M out of N Objects [G6]’, Communications of the Association for Computing Machinery 13:6:368 (1970).

See the C implementation by Matthew Belmonte (and original license), twiddle.c in the src directory. Downloaded from https://netlib.org/toms-2014-06-10/382, 2023-02-19. This implementation is largely a transliteration from the C.

Licensed under the Apache-2.0 license.

Build status

Usage

declare(strict_types=1);

error_reporting(E_ALL ^ E_DEPRECATED);

require __DIR__ . "/vendor/autoload.php";

use Leinster\Twiddle;

Generating combinations from an array

Use SetTwiddler to generate combinations from an array:

<<common-pulled-in-by-noweb>>

$k = 2;
$twiddler = new Twiddle\SetTwiddler($k, [0, 1, 2]);
foreach ($twiddler as $combination) {
    printf("%s\n", json_encode($combination));
}

[1,2]
[0,2]
[0,1]

You can use toArray rather than iterating:

<<common-pulled-in-by-noweb>>

$k = 2;
$twiddler = new Twiddle\SetTwiddler($k, ["A", "B", "C"]);
printf("%.0f\n", $twiddler->count());
printf("%s\n", json_encode($twiddler->toArray()));

3
[["B","C"],["A","C"],["A","B"]]

Duplicate values in the input array are treated as distinct, clients should supply unique values if required:

<<common-pulled-in-by-noweb>>

$k = 2;
$twiddler = new Twiddle\SetTwiddler($k, [0, 0, 1]);
printf("%s\n", json_encode($twiddler->toArray()));
$twiddler = new Twiddle\SetTwiddler($k, ["A", "B", "B"]);
printf("%s\n", json_encode($twiddler->toArray()));

[[0,1],[0,1],[0,0]]
[["B","B"],["A","B"],["A","B"]]

The count method returns ${n \choose k}$ as a float.

<<common-pulled-in-by-noweb>>

$k = 10;
$twiddler = new Twiddle\SetTwiddler($k, range(0, 999));
printf("%.0f\n", $twiddler->count());
printf("%d\n", PHP_INT_MAX);

263409560461970249875456
9223372036854775807

Generating bit sequences

You can use BitTwiddler to generate $n$ length arrays containing $k$ ones and $(n - k)$ zeros:

<<common-pulled-in-by-noweb>>

$k = 2;
$n = 4;
$twiddler = new Twiddle\BitTwiddler($k, $n);
printf("%.0f\n", $twiddler->count());
foreach ($twiddler as $combination) {
    printf("%s\n", json_encode($combination));
}

6
[0,0,1,1]
[1,0,0,1]
[0,1,0,1]
[0,1,1,0]
[1,0,1,0]
[1,1,0,0]

Parameter restrictions

In both cases, and with $n$ the length of $set for SetTwiddler, we must have $k ∈ \mathbb{N}^0,\ n ∈ \mathbb{N}^+,\ k ≤ n$.

Transformers

You can use the transformer functions (or another callable) to modify the output from the generators.

<<common-pulled-in-by-noweb>>

use function Leinster\Twiddle\Functions\stringTransformer;

$twiddler = new Twiddle\SetTwiddler(
    2,
    str_split("ABCDEFG"),
    stringTransformer()
);
printf("%s\n", json_encode($twiddler->toArray()));

["FG","AG","BG","CG","DG","EG","EF","AF","BF","CF","DF","DE","AE","BE","CE","CD","AD","BD","BC","AC","AB"]

<<common-pulled-in-by-noweb>>

use function Leinster\Twiddle\Functions\intTransformer;

$twiddler = new Twiddle\BitTwiddler(3, 5, intTransformer());
printf("%s\n", json_encode($twiddler->toArray()));

[7,19,11,13,21,25,28,26,22,14]

See also

https://github.com/fabis94/php-twiddle is another PHP implementation.