Questions tagged [combinatorics]

For challenges involving combinatorics.

Filter by
Sorted by
Tagged with
12 votes
4 answers
249 views

Compute number of matrices with appropriate sums

When multiplying monomials in the Milnor basis for the Steenrod algebra, part of the algorithm involves enumerating certain "allowable matrices". Given two lists of nonnegative integers r1, ... ,rm ...
user avatar
  • 2,085
14 votes
16 answers
956 views

Mod 2 Multinomial coefficients

quintopia has posted here a challenge to compute multinomial coefficients (some of the text here is copied from there). There is a fun algorithm to compute multinomial coefficients mod 2. Given a ...
user avatar
  • 2,085
13 votes
5 answers
383 views

Integer triangles with perimeter less than n

Definition An "integer triangle" is one with integer coordinates. For example the following triangle is an integer triangle: ...
user avatar
  • 8,117
22 votes
3 answers
858 views

​L​o​o​p​ ​I​t​

Note: The title of this question should be "Loop It", but because title needs to be at least 15 characters, there are some invisible spaces. This note is such that the challenge can be ...
user avatar
  • 43.1k
19 votes
14 answers
2k views

Is it a shuffle?

Yesterday I asked this question about riffle shuffles. It seems that yesterdays question was a bit too hard so this question is a related but much easier task. Today you are asked to determine if a ...
user avatar
  • 89.4k
19 votes
23 answers
2k views

Single swaps of an array

Inspired by Taken from a question at Stack Overflow. The challenge Given an integer n>1, output all arrays that can be obtained by swapping exactly two entries ...
user avatar
  • 100k
18 votes
2 answers
558 views

How many shuffles

A riffle shuffle is a type of shuffle where the deck is split into two partitions and the partitions are then spliced back together to create a new shuffled deck. The cards are spliced together in ...
user avatar
  • 89.4k
9 votes
4 answers
211 views

Prefixless Palindromes

Write a program or function that takes N, and S and outputs the number of palindromes of length S you can build using an alphabet of size N such that any prefix of size between 2 and S-1 is not a ...
user avatar
  • 101
9 votes
4 answers
295 views

Now we're thinking in n dimensions!

The question: Given an a number n ≥ 2, how many distinct pairs of points on an n-dimensional ...
user avatar
  • 1,543
17 votes
9 answers
845 views

XKCD Calendar Facts

Inspiration. Posted with permission. Print one of the possible XKCD calendar "facts": You can get the raw text and structure from my APL reference implementation or from Explain XKCD's ...
user avatar
  • 28k
17 votes
10 answers
2k views

Enumerate all possible grids of integers with constraints

Problem Consider a square 3 by 3 grid of non-negative integers. For each row i the sum of the integers is set to be r_i. ...
user avatar
20 votes
9 answers
806 views

Hand patterns in a card game

A deck of cards is the Cartesian product of S suits and R ranks. Many, though not all, card games use ...
user avatar
  • 14.7k
5 votes
1 answer
321 views

Bobby's Booby-Trapped Safe

Bobby's booby-trapped safe requires an n-digit code to unlock it. Alex has a probe which can test combinations without typing them onto the safe. The probe responds Fail if no individual digit is the ...
user avatar
  • 2,723
20 votes
8 answers
992 views

Pick-flatten a list

Consider the process of "picking" a nested list. Picking is defined as follows: If the argument is a list, take an element from the list at random (uniformly), and pick from that. If the argument is ...
user avatar
13 votes
10 answers
597 views

Counting Fibonacci Orbits

If we define a Fibonacci-like sequence as fk(n) = (fk(n-1) + fk(n-2)) % k, for some integer k (where % is the modulo operator), the sequence will necessarily be cyclic, because there are only k2 ...
user avatar
29 votes
18 answers
7k views

Don't repeat yourself in Rock-Paper-Scissors

Upon the rumor that Codegolf will have a Rock-Paper-Scissors tournament you look into the topic of square-free words. A word made of the letters R, ...
user avatar
  • 1,717
23 votes
6 answers
641 views

Determine How many Wheels There Are

Non-math explanation This is an explanation that is meant to be approachable regardless of your background. It does unfortunately involve some math, but should be understandable to most people with a ...
user avatar
  • 89.4k
19 votes
7 answers
2k views

Number of distinct non-empty subsequences of binary expansion

A subsequence is any sequence that you can get from another by deleting any amount of characters. The distinct non-empty subsequences of 100 are ...
user avatar
  • 38.8k
4 votes
0 answers
195 views

Those annoying grasshoppers [closed]

The problem #6 of IMO 2009 reads: Let a 1, a 2, a 3, ..., a n, be distinct positive integers and let T be a set of n-1positive integers not containing a 1+a 2+a 3+...+a n, A grasshopper is to ...
user avatar
  • 209
8 votes
6 answers
386 views

Distinct Reversible Primitive Binary Necklaces

Introduction - What is a necklace? A necklace is something that OEIS people are obsessed with. The OEIS challenge has like 5 necklace sequences. A binary necklace of length ...
user avatar
  • 40.3k
19 votes
21 answers
2k views

How many partitions do I have?

The partition number of a positive integer is defined as the number of ways it can be expressed as a sum of positive integers. In other words, the number of integer partitions it has. For example, the ...
user avatar
12 votes
19 answers
964 views

Restricted Integer Partitions

Pk(n) means the number of partitions of n into exactly k parts. Given n and ...
user avatar
  • 5,321
13 votes
3 answers
901 views

How many ways can a road cross a river?

Imagine a straight river and a road that goes across the river n times through bridges. The road does not loop on itself and is infinitely long. This road would be considered an open meander. An open ...
user avatar
  • 16.1k
16 votes
7 answers
1k views

How many partitions contain only perfect squares?

Given a non-negative integer or a list of digits, determine in how many ways can the number be formed by concatenating square numbers, which may have leading zeroes. Examples ...
user avatar
  • 40.3k
9 votes
4 answers
594 views

Maximum number of distinct substrings

Description Given a length n, and an alphabet size k>0, your program must determine the number of strings with those ...
user avatar
  • 3,195
15 votes
6 answers
1k views

BASKETBALL FRVR?

You might already be familiar with the game: Basketball FRVR in facebook. There are two types of score you can make: A virgin-shot:(we call it so in our country :D) When the ball enters the basket ...
user avatar
  • 2,759
12 votes
3 answers
396 views

Lyndon word factorization

Background A Lyndon word is a non-empty string which is strictly lexicographically smaller than all its other rotations. It is possible to factor any string uniquely as the concatenation of Lyndon ...
user avatar
  • 3,195
11 votes
27 answers
999 views

All non-ordered pairs between the elements of an array

Task: Return an array with all possible pairs between the elements of an array. Example From a=["a", "b", "c", "d"]; return ...
user avatar
10 votes
2 answers
552 views

Compute OEIS A005434

The task is to compute OEIS A005434 as quickly as possible. Consider a binary string S of length n. Indexing from ...
user avatar
12 votes
14 answers
1k views

How many ways to write numbers as sums of squares?

Task Given two integers \$d\$ and \$n\$, find the number of ways to express \$n\$ as a sum of \$d\$ squares. That is, \$n = r_1^2 + r_2^2 + ... + r_d^2\$, such that \$r_m\$ is an integer for all ...
user avatar
  • 13.6k
7 votes
3 answers
159 views

Rooting for Trees With the Right Nodes

Background A rooted tree is an acyclic graph such that there is exactly one path from one node, called the root, to each other node. A node v is called the parent ...
user avatar
9 votes
1 answer
595 views

Roll to see all sides!

Let's say you have a 20-sided die. You start rolling that die and have to roll it a few dozen times before you finally roll all 20 values. You wonder, how many rolls do I need before I get a 50% ...
user avatar
  • 12.1k
14 votes
12 answers
1k views

Finding approximate correlations

Consider a binary string S of length n. Indexing from 1, we can compute the Hamming ...
user avatar
15 votes
2 answers
190 views

Find Subset Factors

Let's imagine we have a finite set of positive integers. This set can be represented as a line of dots where each integer present in the set is filled in like a scantron or punch card. For example ...
user avatar
  • 89.4k
25 votes
1 answer
823 views

Maximal discrepancy-2 sequence with minimal entropy

Background As noted in the PPCG challenge Compress a maximal discrepancy-2 sequence – which inspired this challenge – the authors of the paper Computer-Aided Proof of Erdős Discrepancy Properties ...
user avatar
  • 207k
14 votes
9 answers
646 views

Find the Odd odds

Given an unordered collection of positive integers by any reasonable input method, return all of the sub-collections that have an odd number of odd elements (i.e. have an odd total). This is code-...
user avatar
  • 89.4k
20 votes
20 answers
935 views

Compress a maximal discrepancy-2 sequence

Output this binary sequence of length 1160: ...
user avatar
  • 138k
11 votes
22 answers
2k views

Generate all Sublist Partitions

Given a non-empty list of integers, output every possible partitioning of the list where each partition is a non-empty sublist. So for the list [1, 2, 3, 4] the ...
user avatar
  • 23k
20 votes
6 answers
1k views

Anaglot Polygrams

Task Write some code that can be rearranged into n different programs in n different languages each outputting a distinct number from 1 to n. No two languages should be the same however different ...
user avatar
  • 89.4k
1 vote
1 answer
271 views

Self Referential Puzzle - medium 2 [closed]

The following puzzle was asked in puzzling SE. This puzzle is quite hard to solve by hand because every answer depends on another answer. So, for example, a solution with all answers being A does not ...
user avatar
9 votes
4 answers
323 views

Greedily partition the list of combinations with repetition

First, a few definitions: Given n and k, consider the sorted list of multisets, where for each multiset we choose ...
user avatar
25 votes
14 answers
3k views

Reuse your code!

In this challenge we try to solve two important problems at once. They are: Given integers \$a\$ and \$b\$, tell if \$a^b-1\$ is a prime number. Given integers \$a\$ and \$b\$, return \$a\choose b\$. ...
user avatar
  • 5,067
27 votes
1 answer
1k views

Find Diffy Games

A fun game to play if you are bored is the Diffy Game. It is a one player game that is pretty simple and can consume a good deal of your time. The Diffy game works like as follows: You start with a ...
user avatar
  • 89.4k
29 votes
31 answers
3k views

Deranged !Combinatorics: Compute the Subfactorial

The subfactorial or rencontres numbers (A000166) are a sequence of numbers similar to the factorial numbers which show up in the combinatorics of permutations. In particular the nth subfactorial !n ...
user avatar
9 votes
5 answers
2k views

Count the number of Hamming distance sequences

The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. Let P be a binary string of ...
user avatar
13 votes
2 answers
1k views

Count how many distance sequences are far from all others

The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. Let P be a binary string of ...
user avatar
12 votes
16 answers
1k views

Number of string permutations that are palindromes

Your input will be a string consisting of small english letters. Your task is to determine the number of distinct permutations of the original string that are a palindrome. The input string has up ...
user avatar
12 votes
1 answer
436 views

Stable marriage problem

Background Suppose that there are 2*n people to be married, and suppose further that each person is attracted to exactly n ...
user avatar
  • 4,650
20 votes
3 answers
374 views

Rafting Problem (Knapsack variant)

First puzzle from me, suggestions for improvement gladly received! The scenario is; You work as a manager for a whitewater rafting company. Every morning, you are given a list of bookings, and you ...
user avatar
  • 303
19 votes
5 answers
3k views

Necklace splitting problem

Background I was inspired by 3Blue1Brown's recent video about the necklace splitting problem (or as he calls it, the stolen necklace problem) and its relationship to the Borsuk-Ulam theorem. In this ...
user avatar
  • 4,650

1 2 3
4
5
8