Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [combinatorics]

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

4
votes
1answer
52 views

Pick the best combination of n choose k models

Algorithm Let \$M_0\$ denote the null model which contains no predictors. This model simply predicts the sample mean of each observation. For \$k=1,2,\ldots,n\$: Fit all \$n \choose k\...
4
votes
3answers
380 views

Generate parentheses solution

I have coded a solution to build all valid permutations of parentheses. My code is below. I have a question on my code based on a comment by my PEP8 checker. It said that there was no need to ...
4
votes
1answer
49 views

Generate all possible combination of n-pair parentheses

The task is taken from LeetCode Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: ...
15
votes
5answers
36k views

Brute force password cracker

I wrote this script for a proof of concept JavaScript password cracker: ...
2
votes
1answer
46 views

Computing the cost for creating a perfect square (with N = 3)

You are given a square matrix \$A \in \mathbb{ N}^{n,n}\$, this number contains integers from \$1\$ to \$n^2\$. The task is to compute the minimal cost, to change this square into a perfect square. A ...
3
votes
1answer
106 views

Swift function to find a specific set of combinations of 3 digits within a larger integer array

I asked this question on Stack Overflow and was directed here. I'm working on a function that will help me quickly find all the upper structure triads (3-note chord) that I can add to a 4-note 7th ...
1
vote
1answer
52 views

Find the combination of matches which are closest to each other

Problem - Given three sorted arrays find combinations which are closest to each other. example - ...
4
votes
1answer
177 views

Project Euler 76: Counting summations

Project Euler Problem 76 asks: How many different ways can one hundred be written as a sum of at least two positive integers? My code is correct but just works slowly. ...
3
votes
1answer
43 views

Iterative version of a permutations algorithm

For learning purposes, I've written an iterative version of a recursive algorithm for generating the set of permutations for a given set of unique integers. Can I make any improvements to increase ...
2
votes
0answers
21 views

Interleave two lists, preserving the order of elements in their original list

I need to write an OCaml program that return all possible zip of two lists together while preserving the order of the element in each list. For example, if we zip the lists [1;2] and [3;4], we get [[1;...
2
votes
2answers
83 views

Iteratively generating permutations with repetitions

I tried to solve the simple problem of generating all permutations of length n with m distinct elements where repetition is allowed. Doing this recursively took me like 10 minutes: ...
7
votes
2answers
366 views

Compute all the permutations for a given vector of integers

The task is to compute all the permutations for a given vector of integers (but of course the specific integer type is not relevant for the solution) The strategy is based on recursion + iterations ...
4
votes
1answer
198 views

Best way to performance permutations

This has been my white whale for a while, the idea is convert all the symbols to the goal symbol using all the pieces. I did an algorithm like 5 years ago (now is lost) and reach lvl 48 but got stuck ...
1
vote
2answers
43 views

Leetcode Next Permutation in Python

My solution to Leetcode Next Permutation in Python. Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is ...
3
votes
2answers
90 views

Number of possible numbers in roman number string

I just started learning programming a few months ago, and I'm intrigued by Haskell. To learn a bit I tried to adapt some code I have in Java so I can see what are equivalent solutions in Haskell. The ...
1
vote
0answers
50 views

itertools.produce reduced and filtered

I need to generate list of all allowable test combination values of of actor, action and ...
4
votes
2answers
123 views

PermCheck Codility

The following code gets 100% on the PermCheck task on Codility. It should be O(N). The question is: A non-empty array A consisting of N integers is given. A permutation is a sequence ...
5
votes
5answers
735 views

Checking if an integer permutation is cyclic in Java

A an integer permutation array[] is said to be cyclic if and only if we can choose an arbitrary element at position i, move it ...
3
votes
1answer
50 views

Mutative Heap's algorithm (permutations generator) in Clojure

For a side project I'm working on, I need to be able to generate permutations. Instead of relying on an existing library like math.combinatorics, I decided to write ...
6
votes
1answer
4k views

Letter Combinations of a Phone Number

I was asked to code a solution in Python in 15 mins. Print all possible word combinations for a given phone number. Numbers 0 and 1 will not be part of the phone number, the numbers can be repeated, ...
3
votes
2answers
311 views

Print out all possible letter combinations a given phone number can represent

I am working on a problem in which given a 7 digit telephone number, we need to print out all possible combinations of letters that each number could represent. I came up with below code and I was ...
1
vote
1answer
717 views

Insect combinatorics challenge

Below is the problem taken from Berkeley's Cs61A page here Question 9: Insect Combinatorics* Consider an insect in an M by N grid. The insect starts at the bottom left corner, (0, 0), and ...
3
votes
2answers
114 views

Grid search parameter combinations in Python

For a computation engineering model, I want to do a grid search for all feasible parameter combinations. Each parameter has a certain possibility range, e.g. (0 … 100) and the parameter combination ...
14
votes
3answers
2k views

On Knuth's “Algorithm L” to generate permutations in lexicographic order

I needed a method to generate all permutations of given elements, so I decided to implement "Algorithm L (Lexicographic permutation generation)" from Donald E. Knuth, "GENERATING ALL PERMUTATIONS" in ...
2
votes
2answers
245 views

Sequence-based enumeration of permutations with Heap's algorithm

Heap's algorithm is an algorithm to generate all permutations of a given array. It ... generates each permutation from the previous one by interchanging a single pair of elements; the other n−2 ...
0
votes
2answers
430 views

Iterative “counting change” implementation in mit-scheme

Here is my iterative implementation of the Counting change example in SICP. Please note that I'm a beginner, which means I only know the basic syntax for the time being. Requirement: How many ...
2
votes
1answer
52 views

Worker placement in Orleans board game/combinations

I am trying to program the board game Orleans. I am planning on making a computer player that plays randomly at first. The part of the game that I'm struggling to code elegantly at the moment has to ...
1
vote
3answers
190 views

Generate all possible permutations of a string in C++

This is my version of the possible permutations of a string challenge. Please give me feedback or criticism. There are two vectors here: positions and ...
8
votes
2answers
709 views

Generating all permutations of a template pack

AllPermutedPacks<Pack<Types...>>::type is to be the pack of packs consisting of all permutations of Types.... For ...
12
votes
3answers
9k views

Get all combinations of selecting k elements from an n-sized array

Was asked this today in an interview. Didn't see it before, and spent quite a lot of time getting it to work (tricky with all the recursion). The goal was to find all possible combinations of ...
2
votes
3answers
85 views

Counting paths between 3 cities in C++

The task is to make a program that prints out how many possible paths a driver can use to visit three cities so that he visits each city exactly n times. The program must be executed within 1 minute ...
6
votes
1answer
59 views

General nested for

I needed a general-purpose function that accepts some sequence_container<sequence_container<T>> and iterates all permutations of the inner container. To ...
64
votes
9answers
97k views

Generating all combinations of an array

I'm generating all combinations of an array, so for instance, ["a", "b", "c", "d"] will generate: ...
1
vote
1answer
83 views

Python finding next word permutation with function generator

Learning how to use function generators in Python I practiced with the following code that finds the next permutation of a word and then uses this new word as input for the next one until there are no ...
10
votes
3answers
669 views

Master Locksmith

Description Master Locksmith has just finished the work of his life: a combination lock so big and complex that no one will ever open it without knowing the right combination. He's done testing ...
1
vote
1answer
601 views

VBA - recursive combination listing based on Excel columns

I have rewritten a recursive procedure to list combinations of values in Excel columns in a way, that instead of one cell string output, there is an array output to Excel range (one value per cell, ...
5
votes
2answers
275 views

Finding all possible letter combinations from an inputted phone number

Prompt: Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the ...
9
votes
2answers
761 views

Generating the powerset in C

I am solving another problem in leetcode. Given a set, generate all the subsets of the set. Input: [1,2,3] Output: ...
2
votes
2answers
492 views

Generating all permutations of 1 digit, 2 equal letters and 2 different letters efficiently

I created a function that generates all the combinations of 1 digit, 2 equal letters and 2 different letters. I reduced the numbers and letters to make it more easy to calculate: ...
7
votes
3answers
2k views

Finding number of integer partitions

I am trying to find number of integer partitions of given n - number. If I have n == 4, the answer should be 5 because: \$4 = 1+1+1+1\$ \$4 = 2+1+1\$ \$4 = 3+1\$ \$...
5
votes
3answers
326 views

Disjoint cycles of a permutation

Given an element of the permutation group, expressed in Cauchy notation, it is often useful to have it expressed in disjoint cycles (for example to apply the permutation to the keys of a dictionary). ...
3
votes
2answers
2k views

Getting all (forward) permutations of a list of strings

I have the following concise-ish (and working) approach to getting all the forward permutations of a list of string. So with the list: w = ["Vehicula", "Sem", "Risus", "Tortor"] the results ...
2
votes
2answers
68 views

Forming all multiples of 3 using the given digits

I'm working on this kata from Codewars. The task is: Given a certain number, how many multiples of three could you obtain with its digits? Supose that you have the number 362. The numbers that ...
0
votes
2answers
148 views

Lattice path from Project Euler with Python solution

I was trying to solve this problem called lattice path from Project Euler: Count the number of unique paths to travel from the top left to the bottom right of a lattice of squares. How many such ...
2
votes
1answer
562 views

n choose k combination in JavaScript

I was asked to solve a problem for \$\binom{n}{k}\$. I did the following implementation and am wondering if there's any feedback. Input: n = Integer ...
4
votes
1answer
926 views

Recursive implementation of power set in Python

I was doing a recursion problem called power set, and would like to get code review. Here's the problem. ...
18
votes
4answers
3k views

Printing all possible sums of two n-sided dice rolls

For my CS class, we were tasked with writing a program that calculates all the possible results from rolling two n-sided dice. For example, the input of 4 would ...
2
votes
1answer
61 views

Fitter Nearest-Neighbor function with three nested loops

Background Problem Consider a set of students that we want to place into Ng groups each of which contains Ns students. Let's ...
7
votes
2answers
870 views

Generate Letter Combinations of a Phone Number

The task: Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. and my solution: ...
2
votes
1answer
57 views

Total of maximum values in all subarrays

This is the crux of a problem found on one of those code challenge sites. I'm fairly new to programming and this was a difficult challenge. I've attempted to solve this with stacks and calculating ...