Questions on the use of Mathematica in combinatorics, including the Combinatorica add-on package.

learn more… | top users | synonyms

29
votes
4answers
3k 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 ...
5
votes
1answer
179 views

Young Tableaux Miscellanea

I have a problem which is mostly neatly described by using Young Tableaux. Mathematica seems to have these Tableaux built in, except that the Tableaux function is ...
-1
votes
1answer
42 views

Create a list of all functions given a set of arguments

I'm trying to examine some patterns on the permutation of elements in finite element functions. I'd like to create a list of all functions (256 of them) on ...
-1
votes
0answers
11 views

to solve this combinatorial optimization problem [migrated]

\begin{align} &\max_{C,E,S} \begin{aligned}[t] &\sum_{t=1}^{T}\sum_{k=1}^{K}min\left\{{\mu(\alpha_{k},e_{k}(t)),\gamma s_{k}(t)}\right\} \end{aligned} \notag \\ &\text{s.t} \notag \\ ...
6
votes
2answers
127 views

Checking if one partition is a subpartition of another

Say I've got two partitions of an list (not necessarily containing numbers, and not necessarily distinct), and I want to check that one is a subpartition of the other. Let's look at some examples: ...
13
votes
2answers
466 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 = ...
11
votes
5answers
624 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 ...
10
votes
1answer
284 views

Is there a function to generate a minimal clique cover?

This is a graph problem known as the "Clique Edge Cover" or "Intersection Number" problem, and the goal is to find, from a given graph like $E=\{\{a,b\},\{a,c\},\{b,c\},\{b,d\},\{c,d\}\}$ and ...
15
votes
7answers
581 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 ...
4
votes
2answers
145 views

How to check whether elements of a list meet a condition without generating the whole list first?

I have to find the number of elements satisfying a given condition from the set: Tuples[Tuples[Tuples[{0,1},n],n],m] The condition for $n=3,m=3$ is: ...
6
votes
3answers
278 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: ...
11
votes
7answers
2k 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 : ...
24
votes
7answers
1k 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 ...
14
votes
3answers
174 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 ...
0
votes
2answers
92 views

Finding permuations in a specific order

I would like to find the following permutations, but need an elegant way of computing it. Ideally I would like to have a variable determine the highest number in the last element and find all ...
4
votes
4answers
178 views

Partition list into a given number of sub-lists

I'm having quite a hard time with the following. I would like to partition a list into a list of sub-lists, in such a way that the number n of sub-lists is fixed. ...
1
vote
0answers
77 views

Is there a minor bug in Neal Alexander's TopologicalSortAll[]?

There is an amazing answer to this question: All possible topological orderings of a graph By Neal Alexander. However, as user "dark blue" (I am not this user) notes: ...
3
votes
2answers
120 views

Can I generate matrices with a constraint?

Say I want a way to generate matrices with the following properties, All non-diagonal elements are either $0,1,-1$ The diagonals are either $k$ or $k+1$ for some $k \in \mathbb{Z}^+$ for some $k$ ...
14
votes
5answers
700 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: ...
2
votes
1answer
99 views

defining Associated Stirling numbers of the Second Kind

First, I'm new to Mathematica. Spent my undergraduate programming with Maple and my computer crashed and I lost it. Fortunately, my university offers free Mathematica downloads to students, so here ...
6
votes
1answer
172 views

Random filling of L-length line with l-length segments

I have discrete L-length line filled randomly with 2-length segments so its cover line with gaps 0 or 1. So we can describe cover configuration as sequence of gaps such as {0,0,1,0,1}. How I can ...
13
votes
5answers
642 views

Permutations[Range[12]] produces an error instead of a list

This input: Permutations[Range[12]] Results in this (error) output: ...
3
votes
2answers
199 views

Constructing a list of Cartesian coordinates of the Icosahedron

I’m learning Mathematica and I need the coordinates of the Icosahedron vertices. This is my attempt at writing a program for it. The vertex coordinates are simply all cyclic permutations and ...
1
vote
2answers
164 views

Permutations with restrictions

I have a problem that can be modeled as: there are 8 boxes in total, and 60 different items. I want to put all items into boxes (all of them can be put into a single box). Now I want to find: 1) ...
4
votes
2answers
887 views

What function returns all possible permutations with repeating list elements?

Let's say I want to find a sample space of such experiment: There are three exits from the box: Left (L), right (R) and front (F). Three mice have been put in that box. Find the sample space of an ...
6
votes
1answer
472 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 ...
0
votes
1answer
120 views

Inclusion-Exclusion Principle Implementation

I would like to know how I can write a Mathematica code for the Inclusion–exclusion principle. The formulas governing it are: $ P(\bigcup_{i=1}^n A_i)=\sum_{k=1}^n (-1)^{k-1} ...
1
vote
2answers
88 views

Numbering of cases implied by a subset of Boolean vectors

In the course of a programming problem I stumbled upon the following sub-problem. Given an arbitrary, but fixed, number of Boolean variables, I would like to be able to pick a subset of the ...
1
vote
0answers
125 views

How to sequentially select, from a large set of tuples (of matrices), those with a certain property

I'm interested in finding a computationally efficient way for selecting all tuples of matrices which have a certain property. The property I'm interested in is that I want the column sum, of f[the ...
4
votes
2answers
129 views

How to obtain all the distinct De Bruijn sequences?

In combinatorial mathematics, a $k$-ary De Bruijn sequence $B(k, n)$ of order $n$ is a cyclic sequence of a given alphabet $A$ with size $k$ for which every possible subsequence of length $n$ in $A$ ...
2
votes
2answers
314 views

Making a flag with six vertical stripes

A flag is to be made with six vertical stripes by using colours yellow, blue, green and red in such a way that no two adjacent stripes should have the same colour. In how many ways is this possible? ...
4
votes
1answer
119 views

The algorithm of ListGraphs[n,m]

I'm not sure if this is a Mathematica problem, math problem or a CS problem, so if this is off-topic please transfer it. In the package Combinatorica there is a ...
2
votes
1answer
103 views

Symbolic multiplicative partitions

Let $p_n\#\equiv\prod_{k=1}^{n}p_k$ (primorial): p[n_] := Times @@ Prime[Range[n]] then the multiplicative partitions of $p_{1,2,3,4}\#$ are $$ \{\{2\}\},$$$$ ...
2
votes
1answer
124 views

How to compute the `Automorphisms` of graphs with multiple edges?

I try to compute the Automorphisms of graphs with multiple edges from its AdjacencyMatrix but failed. The following code shows ...
0
votes
1answer
59 views

How should my data be formatted for use with BetweennessCentrality?

A few weeks ago I asked this question. I am trying to upload my data which is an adjacency list for an undirected, unweighed graph and find the betweenness centrality. At the time I tried to use the ...
0
votes
1answer
160 views

How do I upload a graph as an adjacency list and find the betweenness centrality?

I have an undirected simple graph in a .txt file formatted as an adjacency list like this: 100 200 200 300 300 400 500 600 700 800 900 ... Every number is a node ...
0
votes
1answer
279 views

Generating all “from n choose k” configurations of a simple list [closed]

Suppose that I have a 1-D list called myList. Here's an example: myList = {"A", "B", "C", "D"}; I want to write (or find ...
3
votes
1answer
396 views

Combinatorica Graph from Edge List

Can someone provide an example of a Combinatorica-based graph which uses ShowGraph and Graph and takes in an explicitly defined list of edges (not some auto-generated graph). I have not been able to ...
6
votes
2answers
271 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 ...
1
vote
2answers
191 views

Mathematica can't minimize a function

Mathematica seems not to be able to minimize this univariate function over integer arguments, $r>2, r \in \mathbb{Z}$. ...
6
votes
3answers
225 views

Enumerate the 1-factors (perfect matchings) of $K_n$

Introduction I would like to enumerate the 1-factors, or (near-)perfect matchings, of the complete graph Kn. The adjacency list representation for Kn is basically { (x, y) | 1 ≤ x < y ≤ n }. For ...
2
votes
2answers
87 views

Checking connectedness of a graph

I am trying to use the Combinatorica package in a Mathematica version 8 in the following code: ...
1
vote
2answers
992 views

Create simple table with function of column values

I just want to create a simple table: Three input columns, one output column Call the inputs {x,y,z}, each can take values ...
6
votes
1answer
196 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 ...
4
votes
3answers
156 views

Permutation count for sets with multiplicities

I am able to do a permutation counr for the set {a, a, b} which gives me 3 groups. I am happy with that result. However, if the set is ...
3
votes
7answers
372 views

Concise way to generate multiset lists

I wrote the following to generate a multiset with the same number of items over a fixed range: ConstantArray[#, 3]& /@ Range[9] // Flatten ...
6
votes
1answer
230 views

Shortest polygonal path

I'd like to find the shortest distance between some points (every point must be visited), such as between these 3 points: ...
0
votes
1answer
104 views

How can I find the derivative of a combinatorial expression? [closed]

I want to differentiate the following equation: n = (nchoosek)*p*(1 - p)^(n - k) After differentiating my result is: ...
1
vote
0answers
72 views

The number of real values assumed by combinations of complex roots of a decic

Define complex conjugate as the pair of complex numbers $a+bi,a-bi$. Assume you have 5 such pairs and they are the 10 roots $x_i$ of a 10th-deg equation with integer coefficients. In general, how many ...