Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [combinatorics]

For challenges involving combinatorics.

0
votes
0answers
75 views

Generate all possible 3x2 matrices that fulfill this condition [closed]

I want to get the number of all possible 3x2 matrices such that Each element of the matrix is either 0, 1, or 2. None of the 3 rows of the matrix has the same elements in all entries (\$a_{i1} \neq ...
35
votes
21answers
4k views

Amount of permutations on an NxNxN Rubik's Cube

Introduction: A 3x3x3 Rubik's Cube has \$43,252,003,274,489,856,000\$ possible permutations, which is approximately 43 quintillion. You may have heard about this number before, but how is it actually ...
13
votes
3answers
359 views

Counting the number of restricted forests on the Möbius ladder of length n

OEIS sequence A020872 counts the number of restricted forests on the Möbius ladder Mn. The Challenge The challenge is to write a program that takes an integer as an input ...
20
votes
8answers
782 views

Cycles on the torus

Challenge This challenge will have you write a program that takes in two integers n and m and outputs the number non-...
6
votes
2answers
283 views

Buy the most appropriate items

A store is having a big sale. If your price reaches $199 or more, you can reduce it by $100. You can buy each product only once. Here's an example list of products: (in order to simplify, the names of ...
6
votes
2answers
349 views

Check if all vowels exist in pairs of strings [closed]

Your program should find the number of string pairs (pairs of 2) that contain all vowels (a e i o u), when given an integer N and ...
13
votes
6answers
306 views

Unique Brick Tilings Within A Rectangle

I was browsing Stackoverflow and saw this question about tiling an MxN rectangle, and I thought it would be great for golfing. Here is the task. Given the dimension M and N, write a program that ...
6
votes
5answers
291 views

Generate the k-ary necklaces of length n

The set of necklaces is the set of strings, where two strings are considered to be the same necklace if you can rotate one into the other. Your program will take nonnegative integers ...
17
votes
1answer
278 views

Partition a square grid into parts of equal area

This challenge is based on the following puzzle: You are given an n by n grid with n cells ...
16
votes
4answers
677 views

Number of \$n\$-carbon alkanes

Given a positive number \$n\$, find the number of alkanes with \$n\$ carbon atoms, ignoring stereoisomers; or equivalently, the number of unlabeled trees with \$n\$ nodes, such that every node has ...
18
votes
9answers
2k views

Partitioning the grid into triangles

Goal The goal of this challenge is to produce a function of n which computes the number of ways to partition the n X 1 grid ...
10
votes
3answers
423 views

Arbitrary Randomness (Speed edition)

Given integer n, calculate a set of n random unique integers in range 1..n^2 (inclusive) ...
26
votes
24answers
3k views

Arbitrary Randomness

Randomness is fun. Challenges with no point are fun. Write a function that, given integer input n, will output a set (unordered, unique) of exactly ...
4
votes
2answers
269 views

Find arrays with distinct subarray sums

Consider an array A of length n. The array contains only integers in the range 1 to ...
7
votes
1answer
797 views

Count arrays that are really unique

This is a follow up to Count arrays that make unique sets . The significant difference is the definition of uniqueness. Consider an array A of length ...
0
votes
4answers
443 views

Fastest algorithm to output array containing all integers in range excluding duplicate digits

Input is a single integer in ascending digit order. The only valid inputs are: 12 123 1234 ...
6
votes
4answers
156 views

Seeking Substantial Subcollections

(thanks to @JonathanFrech for the title) Challenge Write a program or function that, given a collection of positive integers \$S\$ and a positive integer \$n\$, finds as many non-overlapping ...
11
votes
3answers
464 views

Count arrays that make unique sets

This question has a similar set up to Find an array that fits a set of sums although is quite different in its goals. Consider an array A of length ...
9
votes
12answers
1k views

Different combinations possible

Problem Given a value n, imagine a mountain landscape inscribed in a reference (0, 0) to (2n, 0). There musn't be white spaces between slopes and also the mountain musn't descend below the x axis. ...
12
votes
2answers
276 views

Removing points from a triangular array without losing triangles

I have a combinatorics problem that I'd like to put on the OEIS—the problem is that I don't have enough terms. This code challenge is to help me compute more terms, and the winner will be the user ...
19
votes
12answers
2k views

Socket - Plug compatibility

Traveling with electronics is always fun, especially when you need an adapter to charge them. Your challenge is to make planning a trip a little easier by checking if a given plug will be compatible ...
28
votes
4answers
753 views

Smallest region of the plane that contains all free n-ominoes

On Math Stack Exchange, I asked a question about the smallest region that can contain all free n-ominos. I'd like to add this sequence to the On-Line Encyclopedia of Integer Sequences once I have ...
13
votes
12answers
1k views

Fun with strings and numbers

Here's a programming puzzle for you: Given a list of pairs of strings and corresponding numbers, for example, [[A,37],[B,27],[C,21],[D,11],[E,10],[F,9],[G,3],[H,2]]...
16
votes
27answers
3k views

The Unique Padlock PIN List!

Introduction In a private chat, a friend of mine apparently recently stumbled across a security system which has the following two restrictions on its valid pins: Each digit must be unique (that is "...
10
votes
22answers
2k views

Cartesian product of a list with itself n times

When given a a list of values and a positive integer n, your code should output the cartesian product of the list with itself n ...
24
votes
34answers
2k views

Sign-Swapping Sums

Given a nonempty list of positive integers \$(x, y, z, \dots)\$, your job is to determine the number of unique values of \$\pm x \pm y \pm z \pm \dots\$ For example, consider the list \$(1, 2, 2)\$. ...
9
votes
4answers
509 views

Count the number of ways of putting balls into bins

In this task you are given an odd number of white balls and the same number of black balls. The task is to count all the ways of putting the balls into bins so that in each bin there is an odd number ...
16
votes
1answer
314 views

Permutations such that no k+2 points fall on any polynomial of degree k

Description Let a permutation of the integers {1, 2, ..., n} be called minimally interpolable if no set of k+2 points (together ...
3
votes
2answers
75 views

Count stacking sequences [duplicate]

Given a list of stack heights, calculate the number of ways those heights could have been arrived at by stacking blocks one at a time. Shortest code wins. Test cases: ...
16
votes
1answer
292 views

Counting polystrips

Polystrips are a subset of polyominoes conforming to the following rules: each piece consist of 1 or more cells no cell can have more than two neighbours the cells should not enclose a hole Free ...
8
votes
17answers
814 views

Sum of combinations with repetition

Write the shortest code you can solving the following problem: Input: An integer X with 2 <= X and X <= 100 Output: ...
17
votes
8answers
807 views

Conjugate permutations

A permutation of size n is a reordering of the first n positive integers. (meaning each integer appears once and exactly once). Permutations can be treated like functions that change the order of a ...
14
votes
8answers
444 views

Deranged Rearrangements

Your task is to write a computer program such that when it is cut up into lines (split on the newline character) every arrangement of the lines will output a different number between 1 and n! (where n ...
8
votes
6answers
423 views

Alice's Tea Party

There are n places set around a circular table. Alice is sat on one of them. At each place, there's a cake. Alice eats her cake, but it doesn't taste very nice. Then the Mad Hatter comes in. He gives ...
23
votes
26answers
2k views

Find The Rank Of A Word

Definition The rank of a word is defined as the position of the word when all the possible permutations (or arrangements) of its letters are arranged alphabetically, like in a dictionary, no matter ...
12
votes
4answers
229 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 ...
14
votes
16answers
869 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 ...
14
votes
5answers
317 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: ...
22
votes
3answers
802 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 searched for. ...
19
votes
14answers
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 ...
19
votes
23answers
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 ...
18
votes
2answers
462 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 ...
8
votes
4answers
201 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 ...
9
votes
4answers
264 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 ...
16
votes
9answers
687 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 transcript (...
17
votes
10answers
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. ...
19
votes
9answers
745 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 ...
5
votes
1answer
247 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 ...
20
votes
8answers
880 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 ...
13
votes
10answers
549 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 ...