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

learn more… | top users | synonyms

31
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 ...
27
votes
3answers
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 ...
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 ...
17
votes
1answer
719 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
votes
5answers
877 views

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

This input: Permutations[Range[12]] Results in this (error) output: ...
6
votes
1answer
665 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 ...
26
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: ...
26
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 ...
14
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 ...
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
3answers
579 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
votes
1answer
361 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
583 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 ...
6
votes
2answers
440 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...
5
votes
3answers
1k 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: ...
14
votes
3answers
607 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 ...
15
votes
3answers
279 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 ...
16
votes
2answers
598 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
853 views

How to correct my code for solving the Josephus problem?

Problem Decription Recently, I have been reading the book Schaum's Outline of Mathematica (2nd Edition), where I encounted the problem: Flavius Josephus was a Jewish historian of the first ...
11
votes
2answers
981 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 ...
4
votes
2answers
386 views

Combinatorica: Girth[] and FindCycle[] disagreement

Warning: run the following code in a fresh Mma session, as some symbols could be shadowed (depending on your Mma version) While trying to answer this question, I fell into the following: ...
6
votes
1answer
2k 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: ...
4
votes
4answers
535 views

Listing matrices up to symmetry

I am interested in the equivalence relation on N x N binary matrices, in which two matrices are equivalent if one can be obtained by rotating/reflecting the other. I would like to obtain a list ...
8
votes
3answers
252 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 ...
3
votes
3answers
214 views

Permutations on elements a>b && b>c

A={1, 2, 3, 4, 5} Permutations[A, {3}] I need to print all permutations where the first number is bigger than the second and the second number is bigger than the ...
3
votes
7answers
415 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 ...
2
votes
0answers
483 views

Generating a function which outputs possible chemical reactions

I want to make a list of chemical reactions and I write them down in a $\require{mhchem}\LaTeX$ format. They are of the following form $$NA_n^i+MB_m^j \rightarrow \hat NA_{\hat n}^{\hat i}+\hat MA_{\...
1
vote
2answers
306 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}$. ...
10
votes
1answer
141 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 ...
24
votes
1answer
708 views

Efficient lazy weak compositions

In Mathematica all weak k-compositions of integer n can be generated using permutations of integer partitions: ...
17
votes
3answers
473 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 ...
13
votes
2answers
554 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
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 : ...
7
votes
2answers
430 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 ...
17
votes
2answers
423 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
821 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 ...
14
votes
1answer
434 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?
10
votes
4answers
879 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 ...
6
votes
1answer
193 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 ...
6
votes
1answer
197 views

How to efficiently find all combinations of the letters in an alphabet given a condition

Problem: I want to find all unique expressions with n number of terms that contain all the digits (or characters) in alphabet. ...
5
votes
1answer
821 views

How to implement Kemeny-Young method? (rank aggregation problem)

Prehistory I am trying to make some statistical analysis of some experimental data, arises from measurements made ​​on an ordinal scale. I faced with the problem of rank aggregation: to get from ...
12
votes
1answer
2k 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 ...
6
votes
1answer
1k 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 ...
5
votes
4answers
600 views

How can I generate permutations of bit strings with repetition?

How can I write a function which has two parameters and it should generate combination of arbitrary range bits, for example: function[n, k], with ...
5
votes
2answers
249 views

How to define even permutations correctly?

I define even permutations as following, but there may be some error. I use it in two different way and get different output. ...
5
votes
2answers
157 views

Combinatorics: Placed errors

Consider a vector of length n where each element can take one of the values U, X, ...
4
votes
3answers
201 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 ...
1
vote
1answer
256 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 ...
12
votes
4answers
410 views

Equivalent Nested Loop Structure

Consider the following examples: ...