Menu
I need a function that does the same thing as itertools.combinations(iterable, r) in python
So far I came up with this:
{-| forward application -}
x -: f = f x
infixl 0 -:
{-| combinations 2 "ABCD" = ["AB","AC","AD","BC","BD","CD"] -}
combinations :: Ord a => Int -> [a] -> [[a]]
combinations k l = (sequence . replicate k) l -: map sort -: sort -: nub
-: filter (\l -> (length . nub) l == length l)
Is there a more elegant and efficient solution?
971
Below are the steps: Sort the given array. Select the least non-negative value from the above array(say at index idx) using lower_bound() in C++. If a positive value doesn't exist in a given array, then the sum is always negative and none of the K element satisfies the given condition.
We use the idea similar to the subset sum problem for creating possible combinations of K numbers from n numbers: we select each number from 1 to n and recur for two possible cases: The selected number is the part of the solution or included in the set The selected number is not part of the solution or not included in the set
Suppose we use the function findKCombination (int K, int n), which returns output in a 2-D array. Inside the function, we declare two temporary arrays to store all outputs one by one: 1-D array temp [] to store any combination of K numbers. The 2-D array output [] [] to store all possible combinations of K numbers
We have discussed one approach in the below post. Print all possible combinations of r elements in a given array of size n In this, we use DFS based approach. We want all numbers from 1 to n. We first push all numbers from 1 to k in tmp_vector and as soon as k is equal to 0, we push all numbers from tmp_vector to ans_vector.
Given an array of size n, generate and print all possible combinations of r elements in array. For example, if input array is {1, 2, 3, 4} and r is 2, then output should be {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4} and {3, 4}. Following are two methods to do this. We create a temporary array ‘data []’ which stores all outputs one by one.
xs elements taken n by n is
mapM (const xs) [1..n]
all combinations (n = 1, 2, ...) is
allCombs xs = [1..] >>= \n -> mapM (const xs) [1..n]
if you need without repetition
filter ((n==).length.nub)
then
combinationsWRep xs n = filter ((n==).length.nub) $ mapM (const xs) [1..n]
(Based on @JoseJuan's answer)
You can also use a list comprehension to filter out those where the second character is not strictly smaller than the first:
[x| x <- mapM (const "ABCD") [1..2], head x < head (tail x) ]
(Based on @FrankSchmitt’s answer)
We have map (const x) [1..n] == replicate n x so we could change his answer to
[x| x <- sequence (replicate 2 "ABCD"), head x < head (tail x) ]
And while in original question, 2 was a parameter k, for this particular example would probably not want to replicate with 2 and write
[ [x1,x2] | x1 <- "ABCD", x2 <- "ABCD", x1 < x2 ]
instead.
With a parameter k things are a bit more tricky if you want to generate them without duplicates. I’d do it recursively:
f 0 _ = [[]]
f _ [] = []
f k as = [ x : xs | (x:as') <- tails as, xs <- f (k-1) as' ]
(This variant does not remove duplicates if there are already in the list as; if you worry about them, pass nub as to it)
4
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
