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

learn more… | top users | synonyms

29
votes
4answers
4k 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
2k 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 ...
25
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 ...
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 ...
24
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 ...
24
votes
6answers
2k 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: ...
23
votes
1answer
659 views

Efficient lazy weak compositions

In Mathematica all weak k-compositions of integer n can be generated using permutations of integer partitions: ...
21
votes
2answers
880 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 ...
17
votes
3answers
466 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
400 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
774 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
668 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 ...
16
votes
1answer
657 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 ...
15
votes
3answers
249 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 ...
15
votes
2answers
553 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
6answers
497 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 = ...
14
votes
5answers
799 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
585 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
3answers
426 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 ...
14
votes
1answer
428 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
805 views

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

This input: Permutations[Range[12]] Results in this (error) output: ...
13
votes
2answers
518 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 ...
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
406 views

Equivalent Nested Loop Structure

Consider the following examples: ...
11
votes
5answers
666 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
3k 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
417 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
845 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
215 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
468 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
139 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
324 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
2answers
468 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 ...
9
votes
5answers
397 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
951 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 ...
9
votes
2answers
209 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
1answer
510 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
476 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 ...
8
votes
2answers
434 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 ...
7
votes
4answers
417 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
3answers
184 views

generating integer partitions

Mathematica can generate integer partitions of an integer $N$. For example, IntegerPartitions[4] quickly gives ...
7
votes
1answer
316 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
530 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 ...
7
votes
2answers
394 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
3answers
185 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 ...
7
votes
1answer
323 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
457 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
5answers
137 views

Simple Enumeration of Coin Tosses

How do I enumerate a sample space with up to 6 coin tosses where 4 Heads ensures a win. For e.g {HHHH},{HTHHH},{TTHHHH},{HTTHHH} etc.I tried the following but I do not know how to do a variable length ...