All Questions
Tagged with combinatorics algorithms
1,046
questions
1
vote
1
answer
454
views
Combinations of lego bricks figures in an array of random bricks
I have an assignment where a robot should assemble some lego figures of the simpsons. See the figures here: Simpsons figures!
To start with we have some identical sized, different colored lego bricks ...
- 43
0
votes
1
answer
326
views
About showing that the print statement in the pseudocode is executed $C_n$ times
It is an exercise I meet in the book Discrete Mathematics Fifth Edition written by Richard.It is on page 184.It is not my homework!I just learned it by myself but I can't catch up with the solution to ...
- 357
3
votes
1
answer
578
views
Algorithm to Find All Vital Edges in a Minimum Weight Spanning Tree
I am trying to locate an algorithm that can find ALL vital edges (edges whose
deletion strictly increases the cost of the minimum weight spanning tree in the resulting graph) in a minimum weight ...
4
votes
1
answer
893
views
Card Shuffling [SPOJ]
The original question is posted on SPOJ, and included below:
Here is an algorithm for shuffling N cards:
1) The cards are divided into K equal piles, where K is a factor of N.
2) The ...
- 183
14
votes
2
answers
8k
views
Complexity of counting the number of triangles of a graph
The trivial approach of counting the number of triangles in a simple graph $G$ of order $n$ is to check for every triple $(x,y,z) \in {V(G)\choose 3}$ if $x,y,z$ forms a triangle.
This procedure ...
- 5,032
2
votes
1
answer
2k
views
Partitioning a set of integers into 4 subsets with equal subset sums
Given $n (n \leq 20)$ positive integers and each integer is $\leq 10,000$. Can they be partitioned into $4$ subsets such that sum of the subsets are pairwise equal to each other.
I am interested in ...
- 628
14
votes
2
answers
5k
views
For what coinage systems does a greedy algorithm not work in providing change?
For the United States coinage system, a greedy algorithm nicely allows for an algorithm that provides change in the least amount of coins.
However, for a coinage system with 12 cent coins, a greedy ...
- 3,445
2
votes
2
answers
443
views
Organising a Tournament
Imagine the following Problem.
The Student Union wants to organise a tournament with 2k participants ( $k \in \mathbb{N}$ ). There are to be m rounds and in each round players should be paired ...
- 3,116
3
votes
1
answer
552
views
Cube nets hexomino tilings.
I am looking for an $\approx12\times12$ rectangle (small holes and small obtrusions are okay) made entirely of cube net hexominos.
It is my understanding that perfect rectangles, in general, are not ...
13
votes
4
answers
1k
views
Counting (Number theory / Factors)
I'm stuck with this counting problem: I have an expression:
$T = (N!) \times (N!) / D$ where, $D \in [1 - N!]$, i.e. $D$ takes all values from $1$ to $N!$ and I'm to count the number of points where $...
- 231
7
votes
2
answers
277
views
Density of black cells in rule 110
Is there a way to compute the limit of the ratio (number of black cells)/(number of white cells), in the rule 110 or rule 30 automaton? With initial state = 1 black cell.
Simulation of first 120000 ...
- 103
5
votes
1
answer
146
views
$X^A \equiv B \pmod{2K + 1}$
I recently found this problem which asks you to find an algorithm to find all $X$ such that $X^A \equiv B \pmod{2K + 1}$.
Is there something special about the modulus being odd that allows us to ...
- 51
1
vote
1
answer
71
views
Algorithm to find specific set of integers within sorted set
I need an effective algorithm to find a subset of integers within a set that meet the conditions:
The sum of sub-set items <= the "limit"
prefer to pick the subset with maximum values that fit ...
- 11
2
votes
0
answers
400
views
Efficient factorion search in arbitrary base
A factorion in base $N$ is a natural number equal to the sum of the factorials of its digits in base $N$. So, the decimal factorions are:
$1 = 1!$
$2 = 2!$
$145 = 1! + 4! + 5!$
$40585 = 4! + 0! + 5! +...
- 143
2
votes
3
answers
261
views
Calculate the number of strings without more than two succeeding occurrences of any character
Problem:
Given an arbitrary, finite alphabet $\Sigma$ with $|\Sigma| > 1$, define the language
$\qquad L = \{w \in \Sigma^* \mid w \text{ has no subword of the form } aaa, a \in \Sigma\}$.
Let $...
- 21