Questions tagged [combinatorics]
Questions on the use of Mathematica in combinatorics, including the Combinatorica add-on package.
125
questions
7
votes
2
answers
309
views
Stars and Bars representation
How can I visualise/represent "Stars and Bars" in Mathematica?
Say I have $n$ balls and $k$ slots to fill (or not to fill) with balls, e.g. when $n=4$ and $k=4$,
...
- 1,273
7
votes
3
answers
1k
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 ...
- 1,145
7
votes
1
answer
706
views
Efficiently generating tuples with Outer
I'm trying to efficiently generate tuples of lists of objects that satisfy a given criterion. The similar questions that I have found on this website end up finding a specific workaround for the given ...
- 2,469
6
votes
2
answers
566
views
How expand Binomial[n, k] for k >= 6? [closed]
Binomial[n, k] is converted to a polynomial only for k less than 6.
...
- 2,704
6
votes
4
answers
798
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
...
- 355
5
votes
2
answers
202
views
Combinatorics: Placed errors
Consider a vector of length n where each element can take one of the values U, X, ...
- 73
5
votes
2
answers
524
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:
...
- 115k
5
votes
3
answers
273
views
How the solve the parameter of the conjugate permutations
As we know the definition of conjugate permutations is:
$$\exists p \quad p^{-1} \alpha p=\beta$$
When I have an alpha=Cycles[{{1,4},{2,5,6,3}}] and a ...
- 26.3k
5
votes
3
answers
459
views
Find position without iterating
The code below solves for the four value of $m_i$ for a given pair of $(N_m,M_m)$.
where
$$
m_1+m_2+m_3+m_4 = M_m\\
|m_1|+|m_2|+|m_3|+|m_4| = N_m
$$
Edit 2
New Sorting
I have now realised that the ...
- 3,584
4
votes
7
answers
544
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
...
- 4,048
4
votes
1
answer
253
views
NextKSizePartition, or how to partition a set into subsets of size $k$ but incrementally
This question might seem very much like the linked one below but it differs in a very special way; Mr.Wizard suggested I start a new post:
Partition a set into subsets of size $k$
What I want is to ...
- 637
3
votes
2
answers
642
views
list of vectors with prescribed sum
Let $a\in\mathbb{N}^n$ and $k\in\mathbb{N}\!=\!\{0,1,2,\ldots\}$. How can I efficiently generate the list $$\{(a_1,\ldots,a_k); a_1,\ldots,a_k\!\in\!\mathbb{N}^n\!\setminus\!\{0\}, a_1\!+\!\ldots\!+\!...
- 1,155
2
votes
0
answers
675
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,485
1
vote
3
answers
276
views
How to generate the lists of $0 \leq m \leq X$ integer values so these values add up to $X$
This must be basic, but my Mathematica (and overall programming) skill level is too low to find a handy solution:
I need to generate all possible lists of $m$ integers (I call these integers $x_i$'s, ...
- 13
0
votes
1
answer
179
views
How to create all possible permutations? [closed]
there is a problem:
I have 5 letters - a,b,c,d,e and 20 places. I have to use each letter at least once but no more than 10 times. So the result can look like {a,a,a,a,a,a,a,a,a,a,b,b,b,b,b,b,b,c,d,e},...
- 21
19
votes
5
answers
707
views
How to enumerate all possible binary associations?
Suppose I have a list of symbols like:
{a,b,c,d}
I would like to enumerate all possible binary associations (combining symbols and/or sublists pairwise):
...
- 2,257
18
votes
2
answers
813
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 ...
- 5,172
17
votes
2
answers
571
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?
- 949
15
votes
6
answers
868
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 = ...
- 153
14
votes
3
answers
630
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:
...
- 445
14
votes
5
answers
2k
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 ...
- 383
14
votes
6
answers
1k
views
how to permute list of number{1,2,3,...,n},while preserve the order of first m terms as well as the last n-m terms?
For example, starting from {1,2,3,4}, I want to generate all permutations like {1,3,2,4},{1,3,4,2},{3,4,1,2} which preserve the ...
- 161
11
votes
4
answers
3k
views
Cyclic and Non-cyclic Permutations
Mathematica has a built in function to generate all permutations of a given list of elements; Permutations
I can't find an equivalent function to generate cyclic ...
- 1,278
11
votes
1
answer
388
views
Warning in version 11.0 when loading package Combinatorica
After the usual and well-known warning
General::compat: "Combinatorica Graph and Permutations functionality has been superseded
by preloaded functionality..."
...
- 1,333
11
votes
1
answer
1k
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
4
answers
1k
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 ...
- 1,029
10
votes
3
answers
721
views
Permutations of lists of fixed even numbers
Let's say we have this list
list={3,6,5,21,23,76,1,28,96,54,77}
I would like to know the number of permutations when every even number stays where it is and ...
- 6,637
10
votes
1
answer
178
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 ...
- 395
9
votes
6
answers
623
views
generating tuples of ones and zeroes with a fixed number of ones
I would like to generate all the tuples of ones and zeros of a given length and with a given number of ones without generating all the possible tuples, which is impossible for tuples of large enough ...
- 637
9
votes
2
answers
2k
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 more valid ...
- 389
8
votes
2
answers
653
views
Tools for finding minimal or almost-minimal graph vertex colorations in Mathematica v9?
I'm looking to compute minimum vertex colorations (s.t. no two vertices of the same color share an edge: http://en.wikipedia.org/wiki/Graph_coloring) for graphs in Mathematica v9 with potentially up ...
- 133
8
votes
4
answers
534
views
Climbing/Descending the Integer Ladder
A fun combinatoric puzzle that's popped up in my work that I think would be cute to have a Mathematica solution to, if anyone wants to give it a go. It's basically a ladder climbing/descending problem ...
- 46.6k
8
votes
4
answers
707
views
Design a function that gives all strict partitions of an integer
A strict partition of an integer has all distinct parts. There are no duplicates like 1 in {5,3,1,1} for 10. All the parts are unique. Sylvester created a bijection between the partitions of an ...
- 1,663
8
votes
1
answer
167
views
Merge list repeating elements
Suppose I have a list with mixed elements
{{{a,b},{c,d}},{{e,f},{h,i}}}
Is there a way so that I can reshuffle the elements to get the following?
...
7
votes
2
answers
1k
views
Defining Associated Stirling Numbers of the Second Kind
First, I'm new to Mathematica. I spent my undergraduate programming with Maple, and my computer crashed and I lost it. Fortunately, my university offers free Mathematica downloads to students, so ...
- 501
7
votes
3
answers
1k
views
How many graphs are there on 4 nodes with degrees 1, 1, 2, 2?
I know just the basic operations on graphs using Mathematica. But I want to know how to write a code that prints all the possible combinations of a graph with a specified number of edges.
Take for ...
- 135
7
votes
3
answers
239
views
Permutations with subsets not containing the same elements
I would like to define a function of two integer variables $ \{n, k\} $, with $ k | n $, that would print all the possible permutations of the first $ n$ positive integers, such that the subsets of $ ...
- 245
7
votes
1
answer
333
views
How to efficiently compute all trees with n leaves and 2n-2 nodes
I would like to efficiently compute all trees with n leaves and 2n-2 nodes. This is equivalent to trees with n leaves where all interior (non-leaf) vertices are trivalent.
The input should be the ...
- 725
6
votes
4
answers
285
views
How to express permutation as the least number of exchanges
If there are grammatical or terminological errors in the following description, please help correct:
In some problems, it is necessary to find out what minimum number of exchanges can change a list ...
6
votes
3
answers
861
views
Duplicate Permutations with Tuples
Permutations without repetition
(in Italian: simple dispositions)
Permutations[{a, b, c, d}, {3}]
or
...
- 4,422
6
votes
1
answer
101
views
Splitting a set of integers over a set of bins
I have a problem that feels like it should be simple but I'm just drawing a blank on. I've got a set of integers, e.g.
...
- 46.6k
6
votes
1
answer
256
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 ...
- 3,401
6
votes
1
answer
450
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.
...
- 802
6
votes
1
answer
2k
views
Efficiently find all connected subgraphs
Is there a way to generate all the connected subgraphs of a graph in mathematica without going through all the subsets of the nodes and checking if the subgraph is connected (which will be O(2^N)*O(...
- 443
6
votes
2
answers
719
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.
...
- 1,145
5
votes
1
answer
2k
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 many &...
- 177
5
votes
4
answers
1k
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 ...
- 51
4
votes
2
answers
617
views
Partition a range of integers into triples
Some time ago, I was asked to look at a simple to formulate puzzle. Consider the list of numbers {1,2, ..., 33}. Try to split this list in 11 triples, such that in ...
- 10.1k
4
votes
2
answers
392
views
How to correctly enumerate all the schemes of this cube coloring problem?
This problem is the fifth question of 1996 Chinese High School Mathematics League or Chinese Mathematical Olympiad in Senior:
Choose several colors from the given six different colors to dye six faces ...
4
votes
3
answers
561
views
Scramble matrix under some condition
Assume I have a matrix.
(mat = Partition[Range@9, 3]) // MatrixForm
mat$=\left(
\begin{array}{ccc}
\color\red1 & \color\red2 & \color\red3 \\
\color\...
- 10.5k