Questions tagged [combinatorics]
Questions on the use of Mathematica in combinatorics, including the Combinatorica add-on package.
489
questions
42
votes
6
answers
4k
views
Partition a set into subsets of size $k$
Given a set $\{a_1,a_2,\dots,a_{lk}\}$ and a positive integer $l$, how can I find all the partitions which includes subsets of size $l$ in Mathematica? For instance, given ...
- 4,039
38
votes
3
answers
2k
views
How to load a package without naming conflicts?
This question applies to any package, but I encountered this problem while working with graphs.
There are symbols in the Combinatorica package (such as ...
- 11k
36
votes
4
answers
5k
views
Looking for "Longest Common Substring" solution
I'm looking for robust code to solve the "Longest Common Substring" problem:
Find the longest string (or strings) that is a substring (or are substrings) of two or more strings.
I can just code it ...
- 8,631
35
votes
8
answers
3k
views
Insert $+$, $-$, $\times$, $/$, $($, $)$ into $123456789$ to make it equal to $100$
Insert $+$, $-$, $\times$, $/$, $($, $)$ into $123456789$ to make it equal to $100$.
Looks like a question for pupils, right?
In fact, if the available math symbols are limited to addition ($+$), ...
- 59.6k
34
votes
1
answer
1k
views
Efficient lazy weak compositions
In Mathematica all weak k-compositions of integer n can be generated using permutations of integer partitions:
...
- 14.9k
33
votes
9
answers
2k
views
Faster derangements?
I wonder what is the fastest method to generate derangements?
Both the Combinatorica function and Martin Ender's answer to Permutations of lists of fixed even numbers are based on filtering the ...
- 267k
33
votes
7
answers
3k
views
How to Derive Tuples Without Replacement
Given a couple of lists like a={1,2,3,4,6} and b={2,3,4,6,9} I can use the built-in Mathematica symbol ...
- 1,029
30
votes
6
answers
3k
views
How to improve the performance of solutions to Project Euler (#39)?
This is the problem 39 of Project Euler, which I asked in the chat room two days ago. My original code runs as slowly as snails, and finally I got two answers from JM and Rojo. Unfortunately, both of ...
- 2,461
25
votes
7
answers
2k
views
Permutations[Range[12]] produces an error instead of a list
This input:
Permutations[Range[12]]
Results in this (error) output:
...
- 1,007
25
votes
5
answers
2k
views
What is the fastest way to count square-free words?
Background
A word is a string of letters in an alphabet. A square-free word has no adjacent repeating substring. For example, (in the ternary alphabet of {0,1,2}) the words 00, 012121, and 0212012021 ...
23
votes
7
answers
2k
views
How do I generate the upper triangular indices from a list?
I have some list
{1,2,3}
How do I generate nested pairs such that I get
{{1,2},{1,3},{2,3}}
That is, I'd like a way to ...
- 2,253
23
votes
1
answer
1k
views
Lazy lists of Tuples and Subsets
I'm trying to build a lazy list that evaluates the n'th m-tuple or subset of a given list using Mathematicas ordering without calculating all the Tuples. The purpose is to allow for example the ...
- 14.7k
22
votes
6
answers
963
views
How to generate all possible orderless partitions of a list according to another list?
This question is hard to describe in plain text. So I will post an example and a working code (brute force) to illustrate.
For example I have a list: ...
- 7,751
22
votes
3
answers
1k
views
Solving word search puzzles
I am trying to create a code that can identify the following terms in a grid of letters: MATHEMATICA, STACK, EXCHANGE and USERS.
...
- 9,145
22
votes
3
answers
1k
views
Generating Tuples with restrictions
I am interested in a certain subset of all tuples. Generating all with Tuples and then filtering is wasteful, and will "blow up" very quickly.
For a concrete ...
- 1,521
21
votes
8
answers
3k
views
Shuffle product of two lists
I want to do the following: I have two lists {a_1,...a_n}, {b_1,...,b_n} and I would like to build now all shuffles out of this. This means all unions of these ...
21
votes
2
answers
1k
views
Plotting an Unreasonable Function
Without getting into too much detail, the following (very complicated) function recently appeared as a solution to a combinatorics problem I've been thinking about:
$$P(n) = \frac{52!}{52^{52}} \cdot ...
- 655
19
votes
3
answers
631
views
Improving speed of code computing number of nonrepeating partitions
I need to answer the following for a number of parameters: How many ways can the integer $k$ be written as a sum of $n$ different integers ranging from $1$ to $m$?
My initial attempt was the ...
- 529
19
votes
5
answers
700
views
How to enumerate all possible binary associations?
Suppose I have a list of symbols like:
{a,b,c,d}
I would like to enumerate all possible binary associations (combining symbols and/or sublists pairwise):
...
- 2,207
19
votes
1
answer
3k
views
How to generate all Feynman diagrams with Mathematica?
I'm using the words "Feynman diagrams" for indexing purposes, but the question is in fact purely graph-theoretic.
Given a list n={n1,n2,...} of non-negative ...
18
votes
2
answers
806
views
Count number of sublists with a total not greater than a given max
Suppose I have a list of positive integers:
data={1, 1, 2, 3, 3, 3, 5, 5, 5, 7, 7, 8, 8, 9, 10, 10, 12, 16, 23}
I want to count the number of subsets up to ...
- 5,132
17
votes
4
answers
928
views
Lazy form of Tuples/Outer to loop over list of lists
This is less a question and more asking if someone has implemented this already, with more skill.
I need to perform the Outer-like generalized outer product of a ...
- 1,047
17
votes
8
answers
1k
views
Enumerating tuples from a larger space such that all pairs of values are present at least once
I am trying to write a function that will accept a list of N lists and returns a list of N-tuples that represent all pairs of values from the original N lists at least once. To illustrate with an ...
- 471
17
votes
2
answers
569
views
When to use built-in Graph/GraphPlot vs. Combinatorica
What are the pros and cons of using built-in Graph/GraphPlot (and related) types vs. types in the Combinatorica package?
- 949
16
votes
7
answers
1k
views
Permutations of nested parentheses (Dyck words)
How would I construct a function that outputs Dyck Words?
e.g. - there are 14 words in $\mathcal{D}_{8}$:
...
- 8,322
16
votes
3
answers
1k
views
House of Santa Claus
The house of Santa Claus is an old German drawing game for small children.
You have to draw a house in one line.
You must not lift your pencil while drawing. $\color{red}{\text{You must not repeat a ...
- 11.5k
16
votes
2
answers
6k
views
Finding all partitions of a set
I'm looking for straightforward way to find all the partitions of a set.
IntegerPartitions seems to provide a useful start. But then things get a bit complicated.
...
- 16.5k
16
votes
2
answers
955
views
Generating Gelfand-Tsetlin patterns
I am doing some research on some combinatorial object called GT-patterns.
They are generated from three parts of data.
Two integer, partitions (sequences of weakly decreasing numbers),
$\lambda = \...
- 2,334
16
votes
1
answer
225
views
Is it better to completely forget about the existence of PowersRepresentations?
I noticed that in several cases the performance of PowersRepresentations is hugely worse than that of IntegerPartitions. (Mma 10....
- 733
15
votes
6
answers
840
views
Partitioning an integer into $k$ equal parts
Say I have an integer $M$. Is there a one-line command to create a partition of $M$ into $k$ integers s.t. the difference between any two integers is as small as possible?
For example, with $M = ...
- 153
15
votes
5
answers
1k
views
Getting number of binary digits combinations without "forbidden" patterns
I need to get the number of all combinations of binary digits in an 8-digit binary number, but not including those that follow some "forbidden" patterns like these:
...
user4449
15
votes
3
answers
797
views
Partitioning with constraints on subsets
Given the following data:
constraints = {{11, 2}, {11, 3}, {11, 4}, {11, 6}, {11, 9}, {1, 6}, {5, 6}, {2, 5}};
weights = {3, 7, 3, 2, 4, 2, 2, 2, 3, 2, 1};
I ...
- 84.1k
14
votes
6
answers
2k
views
How to correct my code for solving the Josephus problem?
Problem Description
Recently, I have been reading the book Schaum's Outline of Mathematica (2nd Edition), where I encountered the problem:
Flavius Josephus was a Jewish historian of the first ...
- 515
14
votes
6
answers
965
views
how to permute list of number{1,2,3,...,n},while preserve the order of first m terms as well as the last n-m terms?
For example, starting from {1,2,3,4}, I want to generate all permutations like {1,3,2,4},{1,3,4,2},{3,4,1,2} which preserve the ...
- 161
14
votes
3
answers
751
views
Determining all possible traversals of a tree
I have a list:
B={423, {{53, {39, 65, 423}}, {66, {67, 81, 423}}, {424, {25, 40, 423}}}};
This list can be visualized as a tree using ...
- 9,757
14
votes
3
answers
2k
views
How to count all cliques (not just maximal ones) in graphs?
How can I count the numbers of $r$-cliques in a graph? In other words, the number of triangles, the number of $K_4$, the number of $K_5$ etc. I have tried for example ...
- 561
14
votes
4
answers
4k
views
Finding elementary cycles of (directed) graphs
I need to enumerate all the simple cycles (i.e. elementary cycles where no vertex is repeated other than the starting) of a graph which has both directed and undirected edges, where we can treat the ...
- 549
14
votes
4
answers
788
views
Generating Linear Extensions of a Partial Order
Given a set $S$ and a partial order $\prec$ over $S$, I'm looking for a way to "efficiently" generate a list of linear extensions of $\prec$. Suppose the partial order is given by a ...
- 435
14
votes
1
answer
4k
views
How to apply a permutation to a symmetric square matrix?
Given a symmetric square matrix, how can I apply a permutation to the rows and columns (i.e. the same permutation to both the rows and the columns) such a way that the new structure of the matrix ...
- 46.3k
13
votes
5
answers
845
views
Probability problem -- Rube Goldberg solution?
A user posted this question on StackOverflow which was closed as off topic:
3 people are playing a game with a standard 52 card deck. Each player is given 2 cards each, possible cards and their ...
- 267k
13
votes
3
answers
871
views
Find all permutations with a condition
How can I find all the permutations of {a, b, c} where a + b + c = n?
For instance: if n = 3...
- 233
13
votes
3
answers
606
views
Word Squares and Beyond
A word square is a set of words which, when placed in a grid, read the same horizontally and vertically. For example, the following is an English word square of order 5:
...
- 435
13
votes
1
answer
650
views
Programming a bishop's move on a grid
I am simplifying the question i need too work with, any advice on how to proceed for each step would be appreciated(no answers)
I have a square grid of size a by b, inside the cell is an object that ...
- 363
13
votes
5
answers
2k
views
Find all the possible ways of partitioning a list into a set of pairs of element
I have a list {x1,...,xN} where N is even, and I need to find all the possible ways to split it into pairs of elements, e.g. the ...
- 373
13
votes
2
answers
1k
views
What is the fastest way to get the nth distinct permutation of a list?
What is the fastest way to write a function nthPermutation[xs_List, n_Integer] which is equivalent to Permutations[xs][[n]] but ...
- 2,306
13
votes
4
answers
555
views
Equivalent Nested Loop Structure (combinations_with_replacement)
Consider the following examples:
...
- 5,404
13
votes
2
answers
1k
views
Better way to get Fisher Exact?
I want to perform a Pearson's $\chi^2$ test to analyse contingency tables; but because I have small numbers, it is recommended to perform instead what is called a Fisher's Exact Test.
This requires ...
- 2,080
13
votes
3
answers
361
views
Efficiently generating samples from an urn with maximum per element constraint?
I need to sample from a distribution that is a hybrid of uniform and hypergeometric in the sense that all elements are sampled uniformly until an element reaches some specified maximum observations, ...
- 25.3k
12
votes
7
answers
4k
views
Combination and Permutation
How could I obtain the list of all the groups of 5 numbers taken from Range[12] such that the 2 lists have an empty intersection :
...
- 5,479
12
votes
7
answers
979
views
Generate only unique combinations when input contains duplicates
I have a list with repeated elements, such as
list = {a, a, b, c, c, c}
and I'd like a list of the unique ways to choose 3 elements from it:
...
- 1,253