Questions tagged [combinatorics]
Questions on the use of Mathematica in combinatorics, including the Combinatorica add-on package.
125
questions
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,651
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,049
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,017
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.8k
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 ...
- 11.1k
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.6k
17
votes
4
answers
972
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,057
8
votes
1
answer
1k
views
Finding all length-n words on an alphabet that have a specified number of each letter
For example, I might want to generate all length n=6 words on the alphabet {A, B, C} that have one ...
- 1,073
36
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 ($+$), ...
- 63.5k
33
votes
7
answers
4k
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
14
votes
3
answers
901
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...
- 243
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 ...
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
11
votes
1
answer
1k
views
Alternative to Subsets to generate k-combinations
I need to generare a huge number of k-combinations for a quite big set of numbers (more than 100), so I would avoid Subsets because it requires too much memory (it generates all subsets at once). I ...
- 2,037
7
votes
2
answers
1k
views
Partition a set into $k$ non-empty subsets
The Stirling number of the second kind is the number of ways to partition a set of $n$ objects into $k$ non-empty subsets. In Mathematica, this is implemented as ...
- 1,825
13
votes
4
answers
568
views
Equivalent Nested Loop Structure (combinations_with_replacement)
Consider the following examples:
...
- 5,562
10
votes
1
answer
775
views
Mathematica implementation of Zeilberger's algorithm (previously done in Maple)
I have this Mathematica code:
...
- 2,335
6
votes
3
answers
527
views
Non-descending Tuples
I want to get all the non-descending tuples of a list with given length, for example:
f[{1,2,3,4},{3}]
...
- 643
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 ...
- 270k
24
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,263
21
votes
1
answer
4k
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 ...
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 ...
- 595
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
9
votes
2
answers
8k
views
Is it possible to generate a Hasse diagram for a defined relation?
I'm looking for a way to create a Hasse Diagram from a given partial order binary relation.
The relation will be given explicitly, for example: ...
- 191
8
votes
3
answers
2k
views
Finding all sublists or substrings of a given list/string
Given a list or string, how do I get a list of all (contiguous) sublists/substrings? The order is not important.
Example for lists:
...
- 8,744
4
votes
1
answer
460
views
Exploring all combinations of parameters
I often need to explore a large parameter space, e.g. making dozens of plots using a range of parameters. This looks something like:
...
- 1,854
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:
...
- 15k
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
19
votes
3
answers
644
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
12
votes
2
answers
1k
views
Memory efficient generation and selection of tuples
The short of this question: I need to find a bunch of n-tuples of {0,1} which do not fail to satisfy a set of (non-linear polynomial) equations, without hogging up all of my memory by trying to ...
- 243
9
votes
1
answer
285
views
Generating an efficient way to compute einsum?
Given an einsum like below, how could I generate an efficient computation graph for it?
$$X_{ik} M_{ij}M_{kl} X_{jl}$$
The indices range from $1$ to $d$ and the goal is to minimize computation time ...
- 8,061
6
votes
2
answers
307
views
Challenge: Creating Compilable Permutations Function
As Mathematica's implemented Permutations function is not compilable, I tried to write my very own Permutations implementation, ...
- 2,700
6
votes
3
answers
2k
views
How to find all graph isomorphisms in FindGraphIsomorphism
I found the second definition of the function FindGraphIsomorphism not working.
Here's the definition Mathematica 8 gives:
...
- 519
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
23
votes
6
answers
1k
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,851
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
16
votes
2
answers
995
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,449
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.6k
15
votes
3
answers
811
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.6k
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.6k
14
votes
3
answers
752
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 ...
- 10.4k
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
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
12
votes
2
answers
677
views
Binomial[-1,-1]
According to various sources e.g.
http://www.proofwiki.org/wiki/Definition:Binomial_Coefficient
and Wolfram themselves
http://functions.wolfram.com/GammaBetaErf/Binomial/02/
, the binomial ...
- 233
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,529
11
votes
2
answers
1k
views
Advanced Tupling
I had asked this question before but I guess I did not make the question clear enough and I apologize for that. Here is the problem: Tuples gives me more data than ...
- 1,029
10
votes
2
answers
401
views
Generating set partition diagrams
I recently came across a very nice illustration of set partitions on wikipedia (Partition of a set article)
I need to reproduce this diagram in order to modify some things, does anyone have a good ...
- 8,061
9
votes
6
answers
970
views
Sierpinski carpet with GraphData
Is this graph in the list among the so-called "standard" structures used in GraphData? However, I have not found yet anything like "Carpet" or "Sponge" in the list ...
- 341
8
votes
3
answers
1k
views
Enumerating all connected graphs with 9 vertices
The version of my Mathematica is 10. I generate a connected graph with 9 vertices, but find that it is not included in Mathematica.
...
- 1,145
7
votes
2
answers
768
views
Solving variant of the knapsack/money-changing problem
I'm trying to solve a variant of the knapsack/changing money problem where I have a set of a few numbers and I'm trying to find the linear (integer) combinations of them which are close to a given ...
- 9,572