6
votes
3answers
162 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 ...
1
vote
0answers
67 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 ...
12
votes
4answers
337 views

Equivalent Nested Loop Structure

Consider the following examples: ...
3
votes
7answers
311 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 ...
5
votes
1answer
397 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 ...
3
votes
0answers
64 views

Listing all combinations produced by picking one element from each of several sets [duplicate]

I have a problem like this, I am given the following sets {a,b,c}, {d,e,f}, {h,i,j}. I want to pick one element from each set, and output a list of all the ...
4
votes
4answers
313 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 ...
0
votes
0answers
38 views

Generating partitions of a set with a specified size of the parts [duplicate]

I tried the following (inspired by the answer here) myList = {a, b, c}; Needs["Combinatorica`"]; SetPartitions[myList] and I got this answer, ...
4
votes
2answers
212 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 ...
15
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: ...
2
votes
0answers
289 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 ...
6
votes
1answer
324 views

Find all permutations with reversals / cyclic permutations removed

I have a list of all non-cyclic permutations of n labels. How can I get rid of all elements which are redundant in the sense that they are the inverse of another one. For instance if n=4, the ...
10
votes
3answers
330 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 ...
7
votes
2answers
1k 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. ...
13
votes
3answers
450 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 ...
6
votes
1answer
347 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 ...
20
votes
5answers
1k 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 ...
10
votes
4answers
627 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 ...
20
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 ...
9
votes
4answers
381 views

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

This input: Permutations[Range[12]] Results in this (error) output: ...
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 : ...