FAQ Database Discussion Community


algorithm to get all combinations of splitting up N items into K bins

algorithm,recursion,permutation
Assuming I have a list of elements [1,2,3,4,] and a number of bins (let's assume 2 bins), I want to come up with a list of all combinations of splitting up items 1-4 into the 2 bins. Solution should look something like this [{{1}, {2,3,4}}, {{2}, {1,3,4}}, {{3}, {1,2,4}}, {{4},...

FInd Possible Permutations of Given Numbers whose Multiplication Gives the Required Number

python,permutation,lcm
Questions : A set of digits S separated by space is passed as input. A number N is also passed as the input. The program must find the two numbers N1, N2 from S so that N1*N2 = N and print them. Input Format: The set of digits in S...

Python every possible combination of a string

python,string,recursion,combinations,permutation
Hi so I'm working with python and I'm trying to write a method where given a string, it would find every combination of that string and append it to a list. I'll give the string and show the outcome that I want. string: x = 'god' outcome: lst = ['g',...

Print out all permutations of an Array [duplicate]

java,arrays,algorithm,permutation,factorial
This question already has an answer here: Permutation of array 5 answers I am working on a program, and I have a function that swaps the positions in an Array of length that is input by a user. However, I am trying to figure out how to print out...

Generate random permutation of huge list (in Python)

python,algorithm,iterator,permutation
I'd like to create a random permutation of the numbers [1,2,...,N] where N is a big number. So I don't want to store all elements of the permutation in memory, but rather iterate over the elements of my particular permutation without holding former values in memory. Any idea how to...

Refactoring logic inside if statement to bare minimum

javascript,math,logic,computer-science,permutation
Sometime ago I wrote an educational JavaScript application with SVG (closed-source for a company). At its most basic form the application consisted of two columns (left and right), and each column contained various geometric shapes (squares, triangles, circles, etc.) Each geometric shape in one column could connect (by drawing a...

Generate permutations of a subset of a List>> in C#

c#,list,permutation
Please take a look at the following example code: List<List<KeyValuePair<string, string>>> list = new List<List<KeyValuePair<string, string>>>(); list.Add(new List<KeyValuePair<string, string>>()); list[0].Add(new KeyValuePair<string, string>("Category 1", "Value A")); list[0].Add(new KeyValuePair<string, string>("Category 1", "Value B")); list.Add(new List<KeyValuePair<string, string>>()); list[1].Add(new KeyValuePair<string, string>("Category 2", "Value...

Time complexity of recursive permutation printer

python,algorithm,time-complexity,permutation
While trying to explain recursive algorithms to generate permutations in lexicographic order, I provided this simple algorithm: def permute(done, remaining): if not remaining: print done return sorted_rem = sorted(remaining) l = len(sorted_rem) for i in xrange(0, l): c = sorted_rem[i] # Move to c to done portion. done.append(c) remaining.remove(c) #...

a repeated permutation with limitations

arrays,ruby,permutation
I am trying to generate all possible combinations of certain values in an array of 15 which add up to 50. $a = [3, 4, 1, 2, 5] print $a.repeated_permutation(15).to_a In this case, [2,2,2,2,4,4,4,4,4,4,4,4,4,3,3] [2,2,2,4,2,4,4,4,4,4,4,4,4,3,3] [2,2,4,2,2,4,4,4,4,4,4,4,4,3,3] are all possible answers. After some investigation I realize the code to do this...

Every (specific sized) combination from set/array with no duplicate items

php,arrays,combinations,permutation
Let's say I have set = [1, 2, 3, 4, 5, 6, 7] I'd like the following in return [1, 2, 3, 4, 5] [4, 3, 2, 1, 6] [7, 5, 1, 3, 2].......... Essentially, as the title states I'm looking to generate specific sized combinations from an array but...

Get every permutation of a mathematical expression

java,algorithm,recursion,permutation,dynamic-programming
Task Given a list of numbers Eg: 1, 2, 3. Get every combination of these numbers using the operations of multiplication or addition (*/+) So in the above example the combinations would be 1+2+3 1+2*3 1*2*3 1*2+3 Ive written a basic recursive method to solve it, the way I thought...

How to find all the possible permutations of a matrix in R?

r,algorithm,matrix,permutation
I have a matrix, for example, 5x5. [,1] [,2] [,3] [,4] [,5] [1,] 22 -2 -2 -2 2 [2,] -2 22 2 2 2 [3,] -2 2 22 2 2 [4,] -2 2 2 22 2 [5,] 2 2 2 2 22. As you can see, the matrix is symmetric....

C++ word unscrambler

c++,permutation,word
I'm fairly new to C++, and as an exercise, I'm trying to write a "word unscrambler". That is, I have a large text file full of words that is loaded into a trie. Each trie_node has an array of 27 trie_nodes which are by default NULL unless that element shares...

Find every permutation of an array in Ruby, including permutations with sub arrays

ruby,arrays,permutation
Consider an array: [4, 6, 9] Require all the permutations: (one, two and three digit ones) [[9], [6], [4], [9, 6], [9, 4], [6, 9], [6, 4], [4, 9], [4, 6], [9, 6, 4], [9, 4, 6], [6, 9, 4], [6, 4, 9], [4, 9, 6], [4, 6, 9]] ...

permutations of vectors in matrix in matlab

matlab,matrix,permutation
I have a static matrix from a file: size(data)=[80 5] What I want is to change position of each vector randomly when I use perms like: N = size(data, 1); X = perms(1:N); % # Permutations of column indices Y = meshgrid(1:N, 1:factorial(N)); % # Row indices idx = (X...

Having problems with python's random.shuffle

python,matrix,random,permutation,shuffle
I would like to make a matrix whose lines are different permutations of the following vector= [1,2,3,4,5,10,10,10,10,10] I tried to use the random.shuffle function, but it seems that everytime I use that, It redefines all objects to which it is assigned. For example, I have tried the following: vec=[1,2,3,4,5] for...

Permuting Letters Of A Word - Clarification needed [duplicate]

java,permutation
This question already has an answer here: How to initialize an array in Java? 8 answers I was searching for a method to permute a word in java and came across this code.I'm actually learning it myself and facing some difficulty in understanding certain portions of the code :...

Combinations of variable length with fixed set

haskell,permutation,combinatorics
I have a set of possible colors defined like this: data Peg = Red | Green | Blue | Yellow | Orange | Purple deriving (Show, Eq, Ord) colors = [Red, Green, Blue, Yellow, Orange, Purple] And code which is a combination of colors defined like this: type Code =...

Function that prints all sequences of 32 digits in C

c,binary,numbers,permutation
Sorry for this question but i'm trying to optimize a C function that prints all sequences of 32 digits, such that each digit in the sequence is a 0 or 1, for example : 00000000000000000000000000000000 ... 01010101010101010101010101010101 ... 01000000010000000100000001000000 i did come out with a solution but it have 3...

Permutations with repetition using recursion - JavaScript

javascript,arrays,algorithm,recursion,permutation
I'm working on a recursive algorithm that takes in an array with three different elements (say ['a', 'b', 'c'] and returns a two-dimensional array with all the possible variations with repetition allowed (so [['a', 'a', 'a'], ['a', 'a', 'b'], ['a', 'b', 'b'],...]). However my code fails and I'm not sure...

Python - New list of permutations with omissions

python,permutation
Lets say I have a list of values my_list = [1,2,3,4] I user itertools.permutations to find all combinations of this list perms = itertools.permutations(my_list) Which creates [(1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (1, 4, 2, 3), (1, 4, 3, 2),...

Permutations and grouping in R

r,combinations,permutation
Assume in R we have three columns. The first is a random sample of 1:4 with replacement. The second is 1:4 repeating as needed. The third is just an index. The result should output a pasted combination of the numbers where order doesn't matter and give a count. Please, note...

python: find all Latin Squares of a set (or partial square with fewer columns)

python,algorithm,permutation,combinatorics
EDIT: Thanks to commenter Douglas Zare, I have renamed the title of this post with more appropriate terminology for anybody else who may be looking for something similar. The code from David Eisenstat below was very helpful. ORIGINAL POST: I apologize for the lack of appropriate set theory terminology... but...

Get some permutations in Haskell

haskell,permutation
how can I get conditioned permutations in Haskell? This is my code: perm :: [Int] -> [[Int]] perm [] = [[]] perm xs = [ x:ps | x <- xs , ps <- perm ( xs\\[x] ) ] But I want to get all the permutations that begins with 1....

Shuffle element such that, no element should come at its original index

c#,algorithm,random,permutation,shuffle
I have a list of Object elements SourceList ResultList (Expected) Obj_A Obj_F Obj_B Obj_C Obj_C Obj_G Obj_D Obj_B Obj_E Obj_A Obj_F Obj_B Obj_G Obj_E Shuffle elements in SourceList such that, no element should come at its original index(in SourceList) in ResultList. For Example, in SourceList C is at index 2,...

A Confusing task

python,combinations,permutation,probability
My approach to the problem was as follows- a=[ ] for i in range(7): a.append([0]*7) c=dict() for i in range(7): for j in range(7): a[i][j]=(i,j) for i in range(7): for j in range(7): c[i+j]=tuple((i*j+j+c)) print c But this produces: {0: (0, 0), 1: (1, 0), 2: (2, 0), 3:...

What is the best way for me to search this Product database?

sql,sql-server,algorithm,permutation
I work for an e-commerce company and we recently launched a new website. I am in charge of creating the search algorithm. We are using a SQL Server database. We are using 'tags' to associate products with certain product keywords. I don't want to use any of our actual information...

Probability, expected number

arrays,variables,random,permutation,probability
In an unsorted array, an element is a local maximum if it is larger than both of the two adjacent elements. The first and last elements of the array are considered local maxima if they are larger than the only adjacent element. If we create an array by randomly permuting...

Multiply arrays by arrays in JAVA

java,arrays,xml,permutation
I have for example three arrays (but I can have more) with some values like this: table_1 = [a,b,c]; //three elements table_2 = [d]; //one elements table_3 = [e,f]; //two elements and I want to get that output <test> <test_1>a</test_1> <test_2>d</test_2> <test_3>e</test_3> </test> <test> <test_1>a</test_1> <test_2>d</test_2> <test_3>f</test_3> </test> <test> <test_1>b</test_1>...

PostgreSQL combinations as distinct from permutations

sql,arrays,postgresql,combinations,permutation
Can't figure out how to make combinations of arrays without repetitions. INPUT is an array of n variables LIKE '{A,B,C,D,E}' Variable A is always single array LIKE '{"A"}' or '{"D,C"}' or '{"D,A,B"}' etc.. What I need is to combine INPUT with A(i) EXAMPLE: 1. A = '{"B"}' --> att='{"B,A","B,C","B,D","B,E"}' 2....

Algorithm to find isomorphic set of permutations

c++,c,arrays,algorithm,permutation
I have an array of set of permutations, and I want to remove isomorphic permutations. We have S sets of permutations, where each set contain K permutations, and each permutation is represented as and array of N elements. I'm currently saving it as an array int pset[S][K][N], where S, K...

php - permutation - possible number

php,permutation
already look around but cant find what i want for PHP. just say i have a number : 1234 ( can be splitted first into array ) and i want to get how many number combination possible for 2 digits, 3 digits , and 4 digits for example : possible...

Python generate all n-permutations of n lists

python,algorithm,permutation
I have n lists of different lengths of wich I want to create all possible permutations. so e.g. if a=[1,2] and b=[3,4,5] then I would love to obtain res=[[1,3],[1,4],[1,5],[2,3],[2,4],[2,5]] I've been trying to achieve this using a recursive function, which turned out to be neither very efficient nor very pythonic....

Generate permutations using polymorphic method

c#,polymorphism,permutation
I was recently asked to write a piece of code as part of an interview test. The instructions were : Please write a piece of code that takes as an input a list in which each element is another list containing an unknown type and which returns a list of...

Recursion function -counting permuation and ignoring permutation

c++,recursion,permutation
I am given this problem: We are going over recursion in my class and I do not quite understand it, I was wondering if someone can help me with this problem let c(n) be the number of different group integers that can be chosen from the integers 1 through n-1,...

create specific permutation of a list in python [closed]

python,algorithm,permutation
I'm trying to write a function that would input a list (of pre-determined length) and output the permutation of that list according to my choice of re-ordering. For example, suppose I have the list [1,'a',12,'b','poppy'] and I have the permutation (3,4,5,2,1) Then the function output would be a list with...

Why is my string undefined?

c++,permutation
The error says s is undefined at this point in my code: cout << "Enter the string : "; cin >> s; How can I fix that? Also, another error at my second bracket says "expecting a ;". What can I do to fix that? Here's my full code: #include...

Nested computation of Cartesian-product of dice rolls

python,permutation,itertools,dice,cartesian-product
I'm working on a Python program where I have to come up with all the ways to roll 9 4-sided dice. I've been trying to come up with a more concise way to write this line: for n in [sum([a, b, c, d, e, f, g, h, i]) for a...

Find permutations of list with unique Heads

list,prolog,permutation
I have a list of unique elements, and I want to generate permutations of that list but I only want the elements to be the head of a list once, like this: ?- special_permutation([a,b,c], X). X = [a,b,c] ; X = [b,a,c] ; X = [c,a,b] ; false. ?- special_permutation([a,b,c,d,e],...

All possible combinations of a word

c,string,recursion,permutation
I was in a job interview and they asked me to generate a list of all possible permutations of a given string. My solution was inefficient and the guy that interview me told me that i was supposed to use recursion. Does anyone know this question?

Print all permutation in lexicographic order

c,arrays,algorithm,sorting,permutation
I want to print all permutation of string in lexicographic order. I write this code: void permute(char *a, int i, int n) { if (i == (n-1)) printf("\"%s\"\n", a); else { for (int j = i; j < n; j++) { swap((a+i), (a+j)); permute(a, i+1, n); swap((a+i), (a+j)); } }...

get all possible permutations of words in string using perl script

perl,permutation,word
I have a string like this , how are you , I want to get all possible shuffle of word like how are you are how you you how are you are how are you how how you are How can I make it in perl script , i've tried...

Smallest permutation of given number

python,string,algorithm,permutation
I've got a number as a string and I want to find the smallest number composed of original number digits, i.e. 56340902138765401345 -> 10001233344455566789 I'm converting the string to list and sorting it. num = '56340902138765401345' a = list(num) a.sort() As a number can't start with a zero (but I...

Find Number of combinations possible

java,math,combinations,permutation
There are two letters "X" and "Y". A String of length N needs to be formed using those two letters. How many number of combinations that can be possible where N should start with "Y" and no two or more consecutive "X" will be there? Consider N = 7: I...

finding the number of ways to generate a number

math,combinations,permutation
I am new to permutations and combinations. I am provided with the number n and I can make a number with the help of n+1 digits which are 0,1,...n. I need to find in how many ways I can make the sum n by putting these n+1 digits in n...

How to get all orderings of a list such that the list is equal to another list?

python,algorithm,list,sorting,permutation
I have lists A and B, which can have duplicates, for example: A = ['x', 'x', 7] B = [7, 'x', 'x'] Now I want all index permutations that permute list B into list A: [1, 2, 0] # because [B[1], B[2], B[0]] == A [2, 1, 0] # because...

Get the kth permutation of 1 to n

algorithm,sequence,permutation
I checked from website, this is called unimodal permutation, which defines as a sequence that has only one local maximum. For example n = 5: 12345 12354 12453 12543 13452 13542 14532 15432 23451 23541 24531 25431 34521 35421 45321 54321 Is there an algorithm to get the kth unimodal...

Can't figure out what the generic name of this algorithm is called?

algorithm,recursion,dynamic,combinations,permutation
I just did a Top Coder SRM where there was a question I had problem solving. I am trying to searching online for details of the algorithm but I can't seem to find it. The question went around the lines of: You have an array, for example [12, 10, 4]...

Efficient partial permutation sort in Julia

sorting,permutation,julia-lang
I am dealing with a problem that requires a partial permutation sort by magnitude in Julia. If x is a vector of dimension p, then what I need are the first k indices corresponding to the k components of x that would appear first in a partial sort by absolute...

Heap's algorithm permutation generator

python,algorithm,permutation
I need to iterate over permutations of a tuple of integers. The order has to be generated by swapping a pair of elements at each step. I found the Wikipedia article (http://en.wikipedia.org/wiki/Heap%27s_algorithm) for Heap's algorithm, which is supposed to do this. The pseudocode is: procedure generate(n : integer, A :...

Handling Permutations of If Statements in C#

c#,if-statement,permutation
I have some Lists which store values. Now I want to create If-Statements to handle this but that's to much. For example: if(list1.Count==0 && list2.Count==0) { //do something } if(list1.Count==0 && list3.Count==0) { //do something } if(list1.Count==0 && list2.Count==0 && list3.Count==0) { //do something } so there is a huge...

Lists of lists python recursive permutation

python,recursion,permutation,nested-lists
How do you manipulate a list of list of string in a specific way so that lst = [ [a, b], [c, d, e], [f, a, e] ] # turns into lst = [ [a, b], [b, a], [c, d, e], [c, e, d], [d, c, e],etc...] #there are 14...

Permutations of English Alphabet of a given length

c++,string,permutation,alphabet
So I have this code. Not sure if it works because the runtime for the program is still continuing. void permute(std::vector<std::string>& wordsVector, std::string prefix, int length, std::string alphabet) { if (length == 0) { //end the recursion wordsVector.push_back(prefix); } else { for (int i = 0; i < alphabet.length(); ++i)...

Replace list of permutations with getSymbols data in R

r,time-series,permutation,quantmod
I downloaded some stock data: require("quantmod") s <- c("AAPL", "ADBE", "ADI", "ADP", "ADSK") e <- new.env() getSymbols(s, src='yahoo', from='2015-01-10', env = e ) #get closing prices close <- do.call(merge, eapply(e, function(x) Cl(x))) I found all the pairs of symbol names: #find all the pairwise permutations perm<-combn(s,2) perm [,1] [,2] [,3]...

Python - How to generate permutations of size greater than the number of list elements

python,list,iteration,permutation
Sorry if that title made no sense. What I mean is this: I have a list [A, B, C] and I want all possible permutations of those elements that will fill a list of length 10. [A, B, C] => [A, A, A, A, A, A, A, A, A, A]...

Quick way to find all permutations of a pandas DataFrame that preserves a sort?

python,sorting,pandas,permutation
I have a DataFrame, and I'd like find all the permutations of it that fulfill a simple ascending sort on one of the columns. (There are many ties.) For example, in the following DataFrame df = pd.DataFrame({'name': ["Abe", "Bob", "Chris", "David", "Evan"], 'age': [28, 20, 21, 22, 21]}) I'd be...

C code permutation

c,permutation
Here is a permutation code, however it does not print all possible permutations. only printed is the input. What's wrong with this code? #include <stdio.h> #include <string.h> #include <stdlib.h> int bitmask; char* characters; int characters_count; char* running; int running_count; void permutations() { int i; if (running_count == characters_count) { printf("%s\n",...

Generating permutations of a set with controlled output?

matlab,permutation
Is there an easy way to get the first x permutations of a set? For example a set with 5 characters {a,b,c,d,e} will have 5*5*5*5*5= 3125 permutations output (repetition is allowed e.g. {a,a,a,a,a}) But I would like to have only the first 100 values for example...

c++ iterate through all neighbor permutations

c++,permutation
I have a vector of N objects, and I would like to iterate through all neighbor permutations of this vector. What I call a neighbor permutation is a permutation where only two elements of the original vector would be changed : if I have a vector with 'a','b','c','d' then :...

Permutation algorithm [duplicate]

algorithm,permutation,powerset
This question already has an answer here: Fast permutation -> number -> permutation mapping algorithms 9 answers I have a Hashmap called H1. There are n Hashmap keys for H1. For H1 hashmap, the program will create all the permutations of the powerset {1,2,3,4,...n}. So in other words, if...

Permutation algorithm C++

c++,algorithm,permutation
I try to translate an algorithm that generates all permutations of k out of n in C++ : public void calculerEquipeTOT(ArrayList<Nageur> L, ArrayList<Nageur> F, int k) { if (k == 0) { if (calculerPointsTOT(L) > this.pointsMeilleureEquipe){ this.meilleureEquipe = L; this.pointsMeilleureEquipe = calculerPointsTOT(meilleureEquipe); } } else { for (Nageur x :...

R: generate possible permutation tables by one column

r,combinations,permutation
I have a table that looks like this: Indikaatori nimi Alamkriteerium Kriteerium Skoor 1 Indikaator 1 1.1 1 100 2 Indikaator 2 1.2 1 100 3 Indikaator 3 1.3 1 100 4 Indikaator 4 1.1 1 0 5 Indikaator 5 2.1 2 0 6 Indikaator 6 2.1 2 0 ......

Travelling Salesman - How to find permutations that are not equivalent

java,algorithm,recursion,graph,permutation
We are trying to optimize our brute force method for TSP. It currently runs at (n-1)! but we can reduce it to (n-1)!/2 by ignoring paths which are equivalent. What we can't figure out is how to stop going down branches that will lead to an equivalent path as our...

Indexing a list of permutations in Python

python,indexing,permutation
This code generates the list of all permutations: def permute(xs, low=0): if low + 1 >= len(xs): yield xs else: for p in permute(xs, low + 1): yield p for i in range(low + 1, len(xs)): xs[low], xs[i] = xs[i], xs[low] for p in permute(xs, low + 1): yield p...