Questions tagged [combinatorics]

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

Filter by
Sorted by
Tagged with
21
votes
3answers
1k views

Solving word search puzzles

I am trying to create a code that can identify the following terms in a grid of letters: MATHEMATICA, STACK, EXCHANGE and USERS. ...
20
votes
6answers
651 views

How to generate all possible orderless partitions of a list according to another list?

This question is hard to describe in plain text. So I will post an example and a working code (brute force) to illustrate. For example I have a list: ...
3
votes
1answer
70 views

Cycle index of a graph automorphism group

I want the cycle index of the group of automorphisms of a (say 3 X 3) grid graph. I can produce the elements of the group with: ...
1
vote
1answer
101 views

How to extract the cycle lengths from a permutation [closed]

I want to input: Cycles[{{1, 3, 5}, {2, 4, 6}, {7,8}}] and get something like: {3,3,2}, that is, a list of the cycle lengths in ...
2
votes
1answer
154 views

How to list all binary expression trees with given leaves

If i have a list of leaf nodes and nonleaf nodes with specified arities, how can I effieciently enumerate the possible trees? For example: ...
6
votes
3answers
382 views

Any alternative way to compute IntegerPartitions?

I tried to compute IntegerPartitions[100] using mathematica on my intel core i3 system. the system hangsup everytime. Is there another way to do such a large computation?
-5
votes
1answer
89 views

A Complicate sum with Mathematica, need Help! [closed]

I found the sum shown below in a scientific paper. I need to calculate it. $$\sum_{k_1+k_2+...+k_n=m}{m \choose k_1,\,k_2,\,\ldots,\,k_n}\ f_{k_1}(x)\,f_{k_2}(x)\,...\,f_{k_n}(x),\qquad k_i \in \...
13
votes
6answers
646 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 ...
0
votes
1answer
50 views

Combination of Values: Automated generation [closed]

How can I get a list of combinations for two values (e.g. 0 and a) such as for N=3: {{a,a,a},{a,a,0},{a,0,a},{0,a,a},{a,0,0},{0,a,0},{0,0,a},{0,0,0}} ? I'd like ...
8
votes
4answers
1k 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 ...
4
votes
2answers
219 views

Generating all permutations of labels in an expression

I have some very long and complex expressions which involve a set of $n$ variables, and I want to be able to permute the labels of the variables. I will give a simple example, instead of my awful ...
10
votes
1answer
478 views

Mathematica implementation of Zeilberger's algorithm (previously done in Maple)

I have this Mathematica code: ...
2
votes
1answer
138 views

Consecutive generation of subsets [duplicate]

It is well known that the array of subsets of even small set is very big. This leads to problems with machine memory. Is there an effective way to generate subsets sequentially?
13
votes
3answers
355 views

Efficiently generating samples from an urn with maximum per element constraint?

I need to sample from a distribution that is a hybrid of uniform and hypergeometric in the sense that all elements are sampled uniformly until an element reaches some specified maximum observations, ...
2
votes
1answer
98 views

How to split a SymmetricGroup into some PermutationGroup with smaller GroupOrder

Background I want to get a permutation list, so I use the SymmetricGroup(or use Permutations) to produce it when the ...
4
votes
2answers
195 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 ...
0
votes
1answer
109 views

Accessing the elements in a table is slower than calculating each time?

This is a follow-up of How to accelerate combinations and sum calculations here? I have tried all tricks but when N reaches 35 the time is still intimidating in a 16-core server, which is far better ...
8
votes
1answer
145 views

Generalizing LongestCommonSequence to 3 or more arguments?

The function LongestCommonSequence finds a longest common subsequence between 2 lists. Apparently, this built-in function does not accept more than 2 arguments. How ...
2
votes
1answer
151 views

How to accelerate combinations and sum calculations here?

I have a 4d matrix H defined as below (embedded with combinations and sums) ...
3
votes
1answer
60 views

Returning maxima of multiple sets

I am trying to prove a conjecture which involves the SetParitions[n] function (which requires the Combinatorica package). This function returns a list of all the set partitions of n. I'd like to take ...
16
votes
1answer
210 views

Is it better to completely forget about the existence of PowersRepresentations?

I noticed that in several cases the performance of PowersRepresentations is hugely worse than that of IntegerPartitions. (Mma 10....
2
votes
1answer
142 views

Mathematica doesn't know about the absorption identity? [closed]

The well-known binomial absorption identity states that $$n\binom{n-1}{k-1} = k \binom{n}{k}$$ However, Mathematica gives ...
6
votes
3answers
386 views

How to partition a set with a condition on subsets?

I want to partition a set of $n$ elements into $k$ subsets with a condition For example: partitioning this set {1,...,5} into 3 subsets with this condition: if $|i-j|<d$ then $i$ can't be with $j$ ...
0
votes
0answers
98 views

Enumerating all orientations of an undirected graph

Given an undirected graph $G$, an orientation of $G$ is a directed graph obtained by assigning every edge a direction, a superorientation of $G$ is a directed graph obtained by orienting every edge in ...
1
vote
1answer
113 views

grouping binary vectors into minimal number of sets

I have a set of binary vectors that I would like to group into a minimal number of sets. A set can be formed when it contains all combinations of elements that vary within that set. Example: for <...
1
vote
1answer
82 views

Fast way to compute intersection of equivalence classes

There is a set $S=\{1, 2, \dots, m\}$ and $n$ equivalence relations on the set: $a \sim_i b $, where $a,b \in S$, $i=1, \dots, n$. Now we define $a \sim b$ iff $ a \sim_i b$ $\forall i=1, \dots, n$. ...
4
votes
1answer
305 views

Closed form probability random walk will hit k >=1 times in n steps

I'm using Mathematica to try to solve https://quant.stackexchange.com/questions/24970 and came across what seems like a simple question: if you take a standard random walk of ...
12
votes
4answers
498 views

Lazy form of Tuples/Outer to loop over list of lists

This is less a question and more asking if someone has implemented this already, with more skill. I need to perform the Outer-like generalized outer product of a ...
8
votes
4answers
887 views

Tuples with one “joker” digit? [duplicate]

I'd like to create an array of all possible length 11 combinations of 1, 2, and the number 3, BUT with the number 3 only appearing zero or once in each combination. I tried: ...
10
votes
4answers
376 views

Efficient way to make subsets of list with placeholders

I have an arbitrary list of unique elements: lst = {a, b, c, d} Documentation allows finding subsets with same number of elements, say ...
6
votes
1answer
266 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. ...
4
votes
1answer
446 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
votes
1answer
100 views

Construct all possible sets of pairs [duplicate]

I am looking for a nice way of constructing all possible pairings of a given list. Currently I am using the brute force approach of sieving the 2-partitions of all permutations. ...
4
votes
2answers
258 views

How can I make this code to count Hamiltonian paths faster?

I have this very basic code to count Hamiltonian paths in a graph: ...
20
votes
3answers
999 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 ...
4
votes
2answers
219 views

`IntegerPartitions` without duplicates

I need to apply a function to integer partitions of many integers, but only the partitions without duplicate numbers. Select[IntegerPartitions[n], DuplicateFreeQ] ...
1
vote
1answer
34 views

No of integral solutions with restrictions [closed]

x+y+z+w=n,where x<=w,y<=w. total number of non negative integral solutions of this equation?is there any closed form formula. what is the generalized formula across any number of variables?
1
vote
0answers
80 views

Finding correct combination of functions

I am trying to write code where I have an array $S$ or numbers in any order [5,4,2,1,....] Then I have a specific set of functions that I can write. ...
6
votes
5answers
279 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 ...
7
votes
4answers
539 views

How to make pairs of Young diagrams appear?

I have the following Young diagrams {{{0}, {2}}, {{0}, {1, 1}}, {{1}, {1}}, {{2}, {0}}, {{1, 1}, {0}}} where you can interpret each pair as following: For ...
4
votes
3answers
333 views

Combinatorica and DualPartition function (for a Young diagram)

I am trying to understand how to evaluate the arm and leg functions of a Young tableaux using Mathematica. To do so I need the Combinatorica package. Then apparently the command ...
5
votes
1answer
150 views

Finding the reduced permutations of six numbers

I am trying to use Mathematica to find the following set of permutations: $$\sum_{\rho\in \tilde{S}_{n+2}} {\rm sgn}(\rho)\eta^{\mu_{\rho_{(1)}}\mu_{\rho_{(2)}}} $$ where $$ \tilde{S}_{n+2}:=\{\rho\...
2
votes
2answers
219 views

Refining subset relations

People who do combinatorics (like me) are often faced with the following problem: For a list of combinatorial objects (vectors, permutations graphs,etc.), we know what multi-set of values it ...
5
votes
1answer
88 views

What does the Combinatorica function: NumberOfPermutationsByType return?

I am using Mathematica 9. If I input: NumberOfPermutationsByType[{2, 2, 1, 1}] Mathematica returns 1/8. I was expecting <...
1
vote
0answers
2k views

Exceeding time constraint of 300 seconds when taking coefficients of some expressions from schur polynomial [closed]

I have written a code that takes coefficients of some expressions from schur function, but it seems to take a lot of time, and Mathematica will stop after 300 seconds saying that it's over the time ...
4
votes
1answer
530 views

Random Partitions

I want to write a function RandomPartition to partition a vector of length n into p partitions of varying (random) lengths. For example with ...
2
votes
1answer
4k views

How to get all possible combinations of this list? [closed]

I'm trying to get all possible combinations of {0,-1} for a certain length. So let's say I want length 2. Then I want my output to be ...
3
votes
1answer
378 views

Way to generate all multisets

I have a set $\left\{\{1,2\}, \{3,4\}, \{5,6\}, \{7,8\}\right\}$ (for example) and want to generate all sets of $n$ elements with repetition but without counting the same multiset twice. So I want my ...
2
votes
2answers
757 views

How to find all possible paths with as many edges between two same vertices?

Suppose I have an undirected graph G = Graph[{1 <-> 2, 2 <-> 3, 2 <-> 3, 3 <-> 4}] I used ...
8
votes
3answers
974 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 ...