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 ...
25
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 ...
24
votes
4answers
1k 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
3answers
1k 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 ...
23
votes
5answers
2k 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 ...
21
votes
2answers
867 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 ...
19
votes
6answers
1k views

Insert $+$, $-$, $\times$, $/$, $($, $)$ into $123456789$ to make it equal to $100$

Looks like a question for pupils, right? In fact if the available math symbol is limited to $+$, $-$, $\times$, $/$ then it's easy to solve: ...
17
votes
3answers
442 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 ...
17
votes
2answers
373 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 ...
16
votes
5answers
725 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 ...
16
votes
7answers
627 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 ...
15
votes
3answers
213 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 ...
14
votes
5answers
763 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: ...
14
votes
3answers
568 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 ...
14
votes
2answers
509 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 = ...
14
votes
1answer
409 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?
13
votes
5answers
698 views

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

This input: Permutations[Range[12]] Results in this (error) output: ...
13
votes
1answer
591 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 ...
12
votes
4answers
2k 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 ...
12
votes
4answers
393 views

Equivalent Nested Loop Structure

Consider the following examples: ...
11
votes
5answers
641 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 ...
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 : ...
11
votes
2answers
406 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: ...
10
votes
4answers
811 views

Efficiently Visualising Very Large Data Sets (without running out of memory)

I have put a few really hard problems in combinatorics up against Mathematica 8. I'd have to say that it works really well, until you want to view the data. If you look at my question Advanced ...
10
votes
2answers
208 views

NumberOfSpanningTrees command not working correctly

I am attempting to use the Combinatorica NumberOfSpanningTrees command for all n-cycle graphs from 3 to 30. I am trying to get a ...
10
votes
1answer
1k 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 ...
10
votes
3answers
441 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 ...
10
votes
1answer
138 views

How do I expand StirlingS2[n, 10] in terms of elementary functions?

I know that it is possible to expand StirlingS2[n, 10] in terms of elementary functions of n. I tried ...
10
votes
1answer
294 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 ...
9
votes
5answers
252 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 ...
9
votes
2answers
197 views

Checking if one partition is a subpartition of another

Say I've got two partitions of a 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: ...
8
votes
2answers
2k 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. ...
8
votes
2answers
914 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 ...
8
votes
1answer
426 views

Looking for a package regarding Schur Polynomials and Kostka numbers

I'm currently looking for any Mathematica package that involves Schur polynomials and/or Kostka numbers. More generally, I'd be happy with anything that expands on symmetric polynomials in general. ...
8
votes
1answer
446 views

Mathematica function/package for shuffle permutations

Does anyone knows a way to compute a list of all (p,q)-shuffles in mathematica? For a definition of the shuffle permutations see for example http://ncatlab.org/nlab/show/shuffle I'm dreaming of a ...
7
votes
4answers
381 views

permutation as product of transpositions

How can the permutation that takes{-f, -i, i, -e} into {-e, -i, i, -f} be realised as a sequence of nearest neighbour ...
7
votes
2answers
412 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 ...
7
votes
1answer
264 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 ...
7
votes
2answers
347 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 ...
7
votes
1answer
255 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 ...
6
votes
3answers
372 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: ...
6
votes
3answers
116 views

generating integer partitions

Mathematica can generate integer partitions of an integer $N$. For example, IntegerPartitions[4] quickly gives ...
6
votes
3answers
498 views

Counting the number of a specific type of permutation

In the theory of cumulants of vector-valued random variables, the following types of formulas appear: \begin{equation} \theta^i \theta^{jk} [3] = \theta^i \theta^{jk} + \theta^j \theta^{ik} + \theta^k ...
6
votes
2answers
380 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 ...
6
votes
2answers
181 views

Subsets or Outer?

How do I generate all possible subsets of a list of positive numbers (with at least 1 of them), given that each of these positive numbers subvariates itself on its input value and its multiplicative ...
6
votes
2answers
300 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 ...
6
votes
1answer
230 views

Find exponential generating function from the first few terms

The function FindGeneratingFunction computes the ordinary generating function of a sequence, given a sufficient number of initial terms. I have two questions in ...
6
votes
3answers
273 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 ...
6
votes
1answer
890 views

All possible topological orderings of a graph

TopologicalSort[] returns one of many unique orderings. From wikipedia: if a topological sort does not form a Hamiltonian path, the DAG will have two or ...
6
votes
1answer
184 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 ...