Questions tagged [combinatorics]

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures.

Filter by
Sorted by
Tagged with
5
votes
1answer
411 views

Iterative implementation of K of N variations

Objective: Print all combinations with repetition of k elements out of a set of n elements. ...
2
votes
1answer
3k views

Compute the mean, variance and standard deviation of all pairs, triplets and sets of four

My code sample for finding the mean for the case of pairs is: ...
5
votes
1answer
86 views

Calculating how similar two objects are according to a database

I want to calculate how similar two objects are according to a database. However the code is very slow; it takes around 2 minutes to analyze just 3 objects. How can I speed it up? I have tried to ...
1
vote
1answer
517 views

Using brute force to do large scale permutations and combinations

This problem should self explanatory based on namings of variables and functions. In essence I am doing well over 720*720*90 checks/calculations. Hence, this is taking far, far too long. How do I make ...
2
votes
1answer
466 views

Efficient String permutations calculation in Java

In trying to compute permutations of a given String, what can I do to further improve the code below for memory and/or time efficiency? ...
1
vote
2answers
154 views

Pascal's triangle with libgmp and pthread in C

I have written a program to generate a pascal triangle of predefined size. Code ...
3
votes
1answer
91 views

Shortest code to generate a full mesh of elements

I am trying to find the shortest code that generates a full mesh of the elements fed into it in graphviz format e.g. the full mesh of [0, 1, 2] is: 2 -> 0 2 -> 1 1 -> 0 I have the code below and I ...
3
votes
0answers
300 views

Recursively generate combinations while using Boost Coroutines

I've tried out implementing a combination generator using boost coroutines. It accepts an array of possible values and generates one array at a time for each combination. As a limitation, it only ...
4
votes
1answer
690 views

Permutation index Python

Here is my Python code for finding the permutation index of a given digits and a target number. And by permutation index I mean, for example, given digits ...
2
votes
0answers
57 views

Calculate and plot expected value involving summations and products

I wrote a code to calculate a series of summations and products for a maths assignment I'm doing. The equation is shown below. $$E(\sigma)=[1-(P(\text{$1^{st}$ rejects}) \times P(\text{$2^{nd}$ ...
2
votes
1answer
1k views

Generate all permutations in Clojure

Given a set, generate all permutations: (permutations #{1 4 5}) => ((5 4 1) (4 5 1) (5 1 4) (1 5 4) (4 1 5) (1 4 5)) Here's what I cobbled together: ...
6
votes
3answers
609 views

Comparing algorithms for computing binomial coefficients in Java

I have these 3 different algorithms for computing binomial coefficients (I also had the 4th recursive one, yet I discarded it since it is super slow). The first uses the factorial formula, the second ...
4
votes
1answer
304 views

Generating vertices of the rectified hypercube

The following piece of code generates the vertices of the rectified hypercube in arbitrary dimensions. The 3D case of the rectified hypercube is a cuboctahedron with 12 vertices (±1,±1,0), (±1,0,±1), (...
2
votes
1answer
2k views

Iterative solution for generating all permutations of a string

I know the runtime for generating all permutations is supposed to be \$O(n!)\$. I'm not sure if the code I wrote for it runs in \$O(n!)\$ though. I'm having trouble analyzing its runtime. The ...
1
vote
1answer
111 views

Permutations part two

This is a follow up from this question. The goal is to make some function that can return the number of possible permutations with repetitions. As Gareth pointed out there is a nice formula for this ...
12
votes
3answers
12k views

Counting permutations without repetitions for a number or a string

Can I make the following code faster with minor modifications? It times out on CodeWars website. ...
5
votes
1answer
466 views

Computation of product of permutations

Given a graph \$G = (V,E)\$ with a unique labeling of each vertex, let the transposition \$(i,j)\$ (where \$i,j\$ are the labels on adjacent vertices) represent selecting an edge and swapping the ...
3
votes
1answer
1k views

Find all distinct combinations of letters in a string

I've been preparing for interviews and picking up modern C++. A recent prep question I did was to find all combinations (or distinct subsets) of letters from a string. E.g. ...
2
votes
1answer
2k views

Form every unique combination of the items of a list of lists

I've tried looking some stuff up. I thought it was transposition first, but looking at this, that's not exactly it. I hacked this code together in about 3 hours, stopping frequently due to ...
1
vote
0answers
420 views

Give the variable length permutations (combinations) of a set of strings

This code is a proof-of-concept which I intend to convert into a static utility / helper class. I'm looking at this review from a structure or performance viewpoint. Small detail such as whether it ...
5
votes
2answers
1k views

Given two strings, determine if one is a permutation of the other

After comparing my newbie attempt with other people's answers, I have a couple questions: I've made s1_set the size of s1. I've ...
6
votes
1answer
64 views

Summative Pattern

While playing around with J (link), I found that you can create a sequence of shape N0 N1 ... NK with i. taking a list as its ...
1
vote
0answers
589 views

3D Bin Packing using Java [closed]

This is a follow up question to 3D bin packing in Java ...
4
votes
2answers
675 views

all combinations of all sizes less than N

I want to generate all possible combinations (without duplicates) of all sizes less or equal than \$N\$, so for example if \$N=3\$ I want to generate the following \$\{1\},\{2\},\{3\}, \{1,2\},\{1,3\},...
2
votes
1answer
137 views

Permutations with repetitions algorithm in R

Given a string of length n, print all permutation of the given string. The code bellow generates all permutations (with repetitions) for the given string and stores them in object ...
4
votes
1answer
891 views

Generating permutations in OCaml

...
2
votes
1answer
419 views

3D bin packing in Java

I made some changes to the first code here I wrote and I want to know which one is more correct logically (before the changes or after the changes). It's really hard to manually test these kind of ...
3
votes
2answers
1k views

3D bin packing algorithm using Java?

I wrote a 3D bin packing algorithm but I am still not sure if it is correct or not. I did not follow any code or pseudo-code that's why I would like to know if it is an efficient algorithm for the 3D ...
10
votes
2answers
628 views

Finding all contiguous sublists such that each member appears an even number of times

The program needs to find all contiguous sublists of numbers where the number of occurrences of every member in the contiguous sublist is divisible by 2. The first line of input is N (the number of ...
5
votes
2answers
2k views

Java 8 Stream to produce all permutations of an array using recursion

I want to write a class that returns a Stream of permutations of an int[]. ...
8
votes
5answers
394 views

Pizza Hut math problem #1 in Haskell

I'm currently attempting to learn Haskell after a fair history of imperative programming. When I saw the Pizza Hut Pi Day math problems, I thought the first one would be a good candidate for my ...
2
votes
1answer
122 views

Computing rowMeans for every combination of columns

The data: ...
1
vote
1answer
302 views

Finding Kth Permutation Sequence

I have written a program to display the kth permutation sequence of a string made up of letters 'O' and 'Z' . I tried optimizing it but my code have not passed test cases due to timeout issues.Looking ...
1
vote
1answer
419 views

Characters set permutations with repetitions

The code bellow generates all the permutation(with repetitions) for given character set. Is there any better(simpler, more performant) way to do that? ...
4
votes
1answer
4k views

Finding ways to achieve a target sum using recursion

I need your review and suggestions how to make this code better. I'm just learning recursion and sure that this solution is not ideal. Question: Write a function that given an input array of ...
6
votes
3answers
522 views

Korean word segmentation using frequency heuristic

This a continuation of a previous question. I want to thank Joe Wallis for his help with increasing the readability of my code. Although the changes made by Joe Wallis did increase the speed of the ...
2
votes
1answer
2k views

Round Robin Tournament

RoundRobin is an implementation of the Round-robin style tournament: ...
5
votes
2answers
5k views

Making the same amount from different combinations of coins (top-down approach)

I was reading a typical interview question found here. Given an amount and a list of denominations, count the number of possible ...
3
votes
1answer
100 views

Improving Speeds of Tokenisation of large word list for distinct combinations

I'm having trouble with a current algorithm I'm writing that takes a corpa, a list of characters in sets (1 one or larger) with a frequency number attached to it. Against another list of character ...
6
votes
1answer
413 views

All possible ways of merging two lists while keeping their order

I am writing a function gives all possible ways of merging two ordered lists such that in the merged list, the elements are still ordered according to the elements in their respective starting list. ...
7
votes
2answers
1k views

An iterator returning all possible partitions of a list in Java

Given a list of \$n\$ objects and an integer \$k \in \{ 1, 2, \dots, n \}\$, this iterator generates all possible ways of partitioning the elements in the list into exactly \$k\$ disjoint, non-empty ...
6
votes
1answer
2k views

An iterator returning all possible permutations of a list in Java

I have this class that iterates over all permutations of an input list: PermutationIterable.java: ...
3
votes
2answers
2k views

Generate subsets of k elements from a set of strings

This is the task: Write a recursive program, which prints all subsets of a given set of N words. Example input: words = {'test', 'rock', 'fun'} ...
1
vote
2answers
3k views

Combination generator in Java - 2nd iteration

I have refactored the previous combination generator, and now it is an iterator returning combinations as lists. It hides larger constant factors as the previous version, yet it is really easy to use: ...
1
vote
2answers
120 views

multirange iterator

I'm doing some boring math with lot of sums over lot of variables. So, instead of nesting for loops I have decided to use something like this: ...
7
votes
5answers
1k views

Generate a dictionary of passwords

I have a Python script that generates a dictionary of all possible 3 digit password combinations. It essentially works by just nesting for loops. This is fine, but ...
2
votes
0answers
3k views

Solution to King Kohima problem in Python

King Kohima problem: King Kohima has reserved a new exclusive street for his executive class employees where they can build their homes. He has assigned you to plan that street. You have to ...
4
votes
1answer
1k views

Combination generator in Java

(See the next iteration.) Given a positive \$N\$, the following class generates all possible non-empty sets \$A \in \mathcal{P}(\{0, 1, \dots, N - 1\})\$ in lexicographic order. Also, it provides a ...
8
votes
1answer
165 views

Scala implementation of @rolfl's integer-partitioning algorithm

While reviewing @Martijn's Distinct sums of integers (finding all combinations of positive integers that sum to a given number), I proposed the following solution: ...
2
votes
2answers
236 views

C permutation generator

I am making a permutation generator in c. Any ideas how I can make it faster? ...