Generate all permutations of a list including diferent sizes and repeated elements
up vote
0
down vote
favorite
I wanted to create the function genAllSize ::[a] -> [[a]], that receives a list l and generates all the lists sorted by size that can be built with the elements of the list l; i.e.
> genAllSize [2,4,8]
[,[2],[4],[8],[2,2],[4,2],[8,2],[2,4],[4,4],[8,4],[2,8],[4,8],[8,8],[2,2,2],[4,2,2],[8,2,2], ...
How would you do it? I came up with a solution using permutations from Data.List but I do not want to use it.
list haskell functional-programming permutation
edited Nov 7 at 7:10
Will Ness
42.3k467118
asked Nov 5 at 15:40
Adrià Cabeza Sant'Anna
174
add a comment |
up vote
0
down vote
favorite
I wanted to create the function genAllSize ::[a] -> [[a]], that receives a list l and generates all the lists sorted by size that can be built with the elements of the list l; i.e.
> genAllSize [2,4,8]
[,[2],[4],[8],[2,2],[4,2],[8,2],[2,4],[4,4],[8,4],[2,8],[4,8],[8,8],[2,2,2],[4,2,2],[8,2,2], ...
How would you do it? I came up with a solution using permutations from Data.List but I do not want to use it.
list haskell functional-programming permutation
edited Nov 7 at 7:10
Will Ness
42.3k467118
asked Nov 5 at 15:40
Adrià Cabeza Sant'Anna
174
1
filterM (_ -> [False, True]) [2,4,8]
– Willem Van Onsem
Nov 5 at 15:44
@WillemVanOnsem That doesn't select with replacement.
– chepner
Nov 5 at 15:46
@chepner: aarghh, I missed that part :(
– Willem Van Onsem
Nov 5 at 15:48
That solution does not take in account the possibility of repeated numbers. I did not want to post my solution because it was pretty ugly tho... I even came up with a solution without permutations and it's pretty ugly too
– Adrià Cabeza Sant'Anna
Nov 5 at 16:07
genAllSize x = concat(iterate (z -> genAllSize' z x) []) where genAllSize' l li = foldl (t i -> t++(map(s -> s++[i]) l ) ) [ ] li
– Adrià Cabeza Sant'Anna
Nov 5 at 16:09
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I wanted to create the function genAllSize ::[a] -> [[a]], that receives a list l and generates all the lists sorted by size that can be built with the elements of the list l; i.e.
> genAllSize [2,4,8]
[,[2],[4],[8],[2,2],[4,2],[8,2],[2,4],[4,4],[8,4],[2,8],[4,8],[8,8],[2,2,2],[4,2,2],[8,2,2], ...
How would you do it? I came up with a solution using permutations from Data.List but I do not want to use it.
list haskell functional-programming permutation
edited Nov 7 at 7:10
Will Ness
42.3k467118
asked Nov 5 at 15:40
Adrià Cabeza Sant'Anna
174
I wanted to create the function genAllSize ::[a] -> [[a]], that receives a list l and generates all the lists sorted by size that can be built with the elements of the list l; i.e.
> genAllSize [2,4,8]
[,[2],[4],[8],[2,2],[4,2],[8,2],[2,4],[4,4],[8,4],[2,8],[4,8],[8,8],[2,2,2],[4,2,2],[8,2,2], ...
How would you do it? I came up with a solution using permutations from Data.List but I do not want to use it.
list haskell functional-programming permutation
list haskell functional-programming permutation
edited Nov 7 at 7:10
Will Ness
42.3k467118
asked Nov 5 at 15:40
Adrià Cabeza Sant'Anna
174
edited Nov 7 at 7:10
Will Ness
42.3k467118
asked Nov 5 at 15:40
Adrià Cabeza Sant'Anna
174
edited Nov 7 at 7:10
Will Ness
42.3k467118
edited Nov 7 at 7:10
Will Ness
42.3k467118
edited Nov 7 at 7:10
Will Ness
42.3k467118
42.3k467118
asked Nov 5 at 15:40
Adrià Cabeza Sant'Anna
174
asked Nov 5 at 15:40
Adrià Cabeza Sant'Anna
174
asked Nov 5 at 15:40
Adrià Cabeza Sant'Anna
174
174
1
filterM (_ -> [False, True]) [2,4,8]
– Willem Van Onsem
Nov 5 at 15:44
@WillemVanOnsem That doesn't select with replacement.
– chepner
Nov 5 at 15:46
@chepner: aarghh, I missed that part :(
– Willem Van Onsem
Nov 5 at 15:48
That solution does not take in account the possibility of repeated numbers. I did not want to post my solution because it was pretty ugly tho... I even came up with a solution without permutations and it's pretty ugly too
– Adrià Cabeza Sant'Anna
Nov 5 at 16:07
genAllSize x = concat(iterate (z -> genAllSize' z x) []) where genAllSize' l li = foldl (t i -> t++(map(s -> s++[i]) l ) ) [ ] li
– Adrià Cabeza Sant'Anna
Nov 5 at 16:09
add a comment |
1
filterM (_ -> [False, True]) [2,4,8]
– Willem Van Onsem
Nov 5 at 15:44
@WillemVanOnsem That doesn't select with replacement.
– chepner
Nov 5 at 15:46
@chepner: aarghh, I missed that part :(
– Willem Van Onsem
Nov 5 at 15:48
That solution does not take in account the possibility of repeated numbers. I did not want to post my solution because it was pretty ugly tho... I even came up with a solution without permutations and it's pretty ugly too
– Adrià Cabeza Sant'Anna
Nov 5 at 16:07
genAllSize x = concat(iterate (z -> genAllSize' z x) []) where genAllSize' l li = foldl (t i -> t++(map(s -> s++[i]) l ) ) [ ] li
– Adrià Cabeza Sant'Anna
Nov 5 at 16:09
1
1
filterM (_ -> [False, True]) [2,4,8]– Willem Van Onsem
Nov 5 at 15:44
filterM (_ -> [False, True]) [2,4,8]– Willem Van Onsem
Nov 5 at 15:44
@WillemVanOnsem That doesn't select with replacement.
– chepner
Nov 5 at 15:46
@WillemVanOnsem That doesn't select with replacement.
– chepner
Nov 5 at 15:46
@chepner: aarghh, I missed that part :(
– Willem Van Onsem
Nov 5 at 15:48
@chepner: aarghh, I missed that part :(
– Willem Van Onsem
Nov 5 at 15:48
That solution does not take in account the possibility of repeated numbers. I did not want to post my solution because it was pretty ugly tho... I even came up with a solution without permutations and it's pretty ugly too
– Adrià Cabeza Sant'Anna
Nov 5 at 16:07
That solution does not take in account the possibility of repeated numbers. I did not want to post my solution because it was pretty ugly tho... I even came up with a solution without permutations and it's pretty ugly too
– Adrià Cabeza Sant'Anna
Nov 5 at 16:07
genAllSize x = concat(iterate (z -> genAllSize' z x) []) where genAllSize' l li = foldl (t i -> t++(map(s -> s++[i]) l ) ) [ ] li – Adrià Cabeza Sant'Anna
Nov 5 at 16:09
genAllSize x = concat(iterate (z -> genAllSize' z x) []) where genAllSize' l li = foldl (t i -> t++(map(s -> s++[i]) l ) ) [ ] li – Adrià Cabeza Sant'Anna
Nov 5 at 16:09
add a comment |
3 Answers
3
active
oldest
votes
up vote
4
down vote
- Given an input list
xs, select a prefix of that in a non deterministic way - For each element in the prefix, replace it with any element of
xs, in a non deterministic way
Result:
> xs = [2,4,8]
> inits xs >>= mapM (const xs)
[,[2],[4],[8],[2,2],[2,4],[2,8],[4,2],[4,4],[4,8],[8,2],[8,4],
[8,8],[2,2,2],[2,2,4],[2,2,8],[2,4,2],[2,4,4],[2,4,8],[2,8,2],
[2,8,4],[2,8,8],[4,2,2],[4,2,4],[4,2,8],[4,4,2],[4,4,4],[4,4,8],
[4,8,2],[4,8,4],[4,8,8],[8,2,2],[8,2,4],[8,2,8],[8,4,2],[8,4,4],
[8,4,8],[8,8,2],[8,8,4],[8,8,8]]
answered Nov 5 at 16:09
chi
72.3k280133
1
why is it finite?
– karakfa
Nov 5 at 16:37
@karakfa We only involve finite lists above.xsis finite, soinits xsis finite, and>>=loops over a finite number of finite prefixes.mapMloops over each element (finitely many), and replaces them with an element taken fromxs(finite).
– chi
Nov 5 at 17:07
1
This doesn’t actually use the elements of the results ofinits, just their lengths, so you could write this a bit more explicitly (albeit less elegantly imo) asjoin [sequence $ take n $ repeat xs | n <- [0..length xs]]. Also it’s worth knowing thatmapM (const xs)=sequence . fmap (const xs)=sequence . (xs <$); the expressionx <$ yis handy for replacing all elements in the containerywithxwhile retaining its shape, or running an actiony, discarding its result, and returningx(where you might otherwise writey *> pure x).
– Jon Purdy
Nov 6 at 0:56
add a comment |
up vote
2
down vote
Hmm I guess you a need a lazy infinite list of cycling subsequences. One naive way could be like
Prelude> take 100 $ nub . subsequences . cycle $ [2,4,8]
[,[2],[4],[2,4],[8],[2,8],[4,8],[2,4,8],[2,2],[4,2],[2,4,2],[8,2],[2,8,2],[4,8,2],[2,4,8,2],[4,4],[2,4,4],[8,4],[2,8,4],[4,8,4],[2,4,8,4],[2,2,4],[4,2,4],[2,4,2,4],[8,2,4],[2,8,2,4],[4,8,2,4],[2,4,8,2,4],[8,8],[2,8,8],[4,8,8],[2,4,8,8],[2,2,8],[4,2,8],[2,4,2,8],[8,2,8],[2,8,2,8],[4,8,2,8],[2,4,8,2,8],[4,4,8],[2,4,4,8],[8,4,8],[2,8,4,8],[4,8,4,8],[2,4,8,4,8],[2,2,4,8],[4,2,4,8],[2,4,2,4,8],[8,2,4,8],[2,8,2,4,8],[4,8,2,4,8],[2,4,8,2,4,8],[2,2,2],[4,2,2],[2,4,2,2],[8,2,2],[2,8,2,2],[4,8,2,2],[2,4,8,2,2],[4,4,2],[2,4,4,2],[8,4,2],[2,8,4,2],[4,8,4,2],[2,4,8,4,2],[2,2,4,2],[4,2,4,2],[2,4,2,4,2],[8,2,4,2],[2,8,2,4,2],[4,8,2,4,2],[2,4,8,2,4,2]]
answered Nov 5 at 17:16
Redu
12.5k22435
add a comment |
up vote
0
down vote
This produces the elements in a different order within each length than your example, but it meets the definition of the text of your question. Changing the order is easy - you have to replace <*> with a slightly different operator of your own making.
import Control.Applicative
import Control.Monad
rinvjoin :: Applicative both => both a -> both (both a)
rinvjoin = fmap pure
extendBranches options branches = (<|>) <$> options <*> branches
singletonBranchExtensions = rinvjoin
genAllSize =
genAllSize xs = join <$> iterate (extendBranches extensions) $ initialBranches
where extensions = singletonBranchExtensions xs
initialBranches = pure empty
answered Nov 11 at 10:37
codeshot
7231718
indeed. But I'm going to leave it because I get confused by the myriad of maximally refined concepts and I bet others do too.
– codeshot
Nov 11 at 11:06
My current solution has a problem that it keeps looking for branch extensions forever for genAllSize but where there's a finite answer, the list should be finite, really
– codeshot
Nov 11 at 11:07
genAllSize xs = join $ iterate (liftA2 (<|>) (pure <$> xs)) (pure empty)is write-only, though. Mine needs to be expanded out into more explicit definitions as it is, removing some can't be right.
– codeshot
Nov 11 at 11:09
It's not supposed to do what chi's answer is doing, chi's answer isn't correct
– codeshot
Nov 11 at 11:13
[2,2,2,2] is a list made from some combination of elements from [2,4,8] and yet chi's answer doesn't include it in the output list. My answer correctly includes it.
– codeshot
Nov 11 at 11:22
|
show 5 more comments
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
- Given an input list
xs, select a prefix of that in a non deterministic way - For each element in the prefix, replace it with any element of
xs, in a non deterministic way
Result:
> xs = [2,4,8]
> inits xs >>= mapM (const xs)
[,[2],[4],[8],[2,2],[2,4],[2,8],[4,2],[4,4],[4,8],[8,2],[8,4],
[8,8],[2,2,2],[2,2,4],[2,2,8],[2,4,2],[2,4,4],[2,4,8],[2,8,2],
[2,8,4],[2,8,8],[4,2,2],[4,2,4],[4,2,8],[4,4,2],[4,4,4],[4,4,8],
[4,8,2],[4,8,4],[4,8,8],[8,2,2],[8,2,4],[8,2,8],[8,4,2],[8,4,4],
[8,4,8],[8,8,2],[8,8,4],[8,8,8]]
answered Nov 5 at 16:09
chi
72.3k280133
1
why is it finite?
– karakfa
Nov 5 at 16:37
@karakfa We only involve finite lists above.xsis finite, soinits xsis finite, and>>=loops over a finite number of finite prefixes.mapMloops over each element (finitely many), and replaces them with an element taken fromxs(finite).
– chi
Nov 5 at 17:07
1
This doesn’t actually use the elements of the results ofinits, just their lengths, so you could write this a bit more explicitly (albeit less elegantly imo) asjoin [sequence $ take n $ repeat xs | n <- [0..length xs]]. Also it’s worth knowing thatmapM (const xs)=sequence . fmap (const xs)=sequence . (xs <$); the expressionx <$ yis handy for replacing all elements in the containerywithxwhile retaining its shape, or running an actiony, discarding its result, and returningx(where you might otherwise writey *> pure x).
– Jon Purdy
Nov 6 at 0:56
add a comment |
up vote
4
down vote
- Given an input list
xs, select a prefix of that in a non deterministic way - For each element in the prefix, replace it with any element of
xs, in a non deterministic way
Result:
> xs = [2,4,8]
> inits xs >>= mapM (const xs)
[,[2],[4],[8],[2,2],[2,4],[2,8],[4,2],[4,4],[4,8],[8,2],[8,4],
[8,8],[2,2,2],[2,2,4],[2,2,8],[2,4,2],[2,4,4],[2,4,8],[2,8,2],
[2,8,4],[2,8,8],[4,2,2],[4,2,4],[4,2,8],[4,4,2],[4,4,4],[4,4,8],
[4,8,2],[4,8,4],[4,8,8],[8,2,2],[8,2,4],[8,2,8],[8,4,2],[8,4,4],
[8,4,8],[8,8,2],[8,8,4],[8,8,8]]
answered Nov 5 at 16:09
chi
72.3k280133
1
why is it finite?
– karakfa
Nov 5 at 16:37
@karakfa We only involve finite lists above.xsis finite, soinits xsis finite, and>>=loops over a finite number of finite prefixes.mapMloops over each element (finitely many), and replaces them with an element taken fromxs(finite).
– chi
Nov 5 at 17:07
1
This doesn’t actually use the elements of the results ofinits, just their lengths, so you could write this a bit more explicitly (albeit less elegantly imo) asjoin [sequence $ take n $ repeat xs | n <- [0..length xs]]. Also it’s worth knowing thatmapM (const xs)=sequence . fmap (const xs)=sequence . (xs <$); the expressionx <$ yis handy for replacing all elements in the containerywithxwhile retaining its shape, or running an actiony, discarding its result, and returningx(where you might otherwise writey *> pure x).
– Jon Purdy
Nov 6 at 0:56
add a comment |
up vote
4
down vote
up vote
4
down vote
- Given an input list
xs, select a prefix of that in a non deterministic way - For each element in the prefix, replace it with any element of
xs, in a non deterministic way
Result:
> xs = [2,4,8]
> inits xs >>= mapM (const xs)
[,[2],[4],[8],[2,2],[2,4],[2,8],[4,2],[4,4],[4,8],[8,2],[8,4],
[8,8],[2,2,2],[2,2,4],[2,2,8],[2,4,2],[2,4,4],[2,4,8],[2,8,2],
[2,8,4],[2,8,8],[4,2,2],[4,2,4],[4,2,8],[4,4,2],[4,4,4],[4,4,8],
[4,8,2],[4,8,4],[4,8,8],[8,2,2],[8,2,4],[8,2,8],[8,4,2],[8,4,4],
[8,4,8],[8,8,2],[8,8,4],[8,8,8]]
answered Nov 5 at 16:09
chi
72.3k280133
- Given an input list
xs, select a prefix of that in a non deterministic way - For each element in the prefix, replace it with any element of
xs, in a non deterministic way
Result:
> xs = [2,4,8]
> inits xs >>= mapM (const xs)
[,[2],[4],[8],[2,2],[2,4],[2,8],[4,2],[4,4],[4,8],[8,2],[8,4],
[8,8],[2,2,2],[2,2,4],[2,2,8],[2,4,2],[2,4,4],[2,4,8],[2,8,2],
[2,8,4],[2,8,8],[4,2,2],[4,2,4],[4,2,8],[4,4,2],[4,4,4],[4,4,8],
[4,8,2],[4,8,4],[4,8,8],[8,2,2],[8,2,4],[8,2,8],[8,4,2],[8,4,4],
[8,4,8],[8,8,2],[8,8,4],[8,8,8]]
answered Nov 5 at 16:09
chi
72.3k280133
answered Nov 5 at 16:09
chi
72.3k280133
answered Nov 5 at 16:09
chi
72.3k280133
answered Nov 5 at 16:09
chi
72.3k280133
72.3k280133
1
why is it finite?
– karakfa
Nov 5 at 16:37
@karakfa We only involve finite lists above.xsis finite, soinits xsis finite, and>>=loops over a finite number of finite prefixes.mapMloops over each element (finitely many), and replaces them with an element taken fromxs(finite).
– chi
Nov 5 at 17:07
1
This doesn’t actually use the elements of the results ofinits, just their lengths, so you could write this a bit more explicitly (albeit less elegantly imo) asjoin [sequence $ take n $ repeat xs | n <- [0..length xs]]. Also it’s worth knowing thatmapM (const xs)=sequence . fmap (const xs)=sequence . (xs <$); the expressionx <$ yis handy for replacing all elements in the containerywithxwhile retaining its shape, or running an actiony, discarding its result, and returningx(where you might otherwise writey *> pure x).
– Jon Purdy
Nov 6 at 0:56
add a comment |
1
why is it finite?
– karakfa
Nov 5 at 16:37
@karakfa We only involve finite lists above.xsis finite, soinits xsis finite, and>>=loops over a finite number of finite prefixes.mapMloops over each element (finitely many), and replaces them with an element taken fromxs(finite).
– chi
Nov 5 at 17:07
1
This doesn’t actually use the elements of the results ofinits, just their lengths, so you could write this a bit more explicitly (albeit less elegantly imo) asjoin [sequence $ take n $ repeat xs | n <- [0..length xs]]. Also it’s worth knowing thatmapM (const xs)=sequence . fmap (const xs)=sequence . (xs <$); the expressionx <$ yis handy for replacing all elements in the containerywithxwhile retaining its shape, or running an actiony, discarding its result, and returningx(where you might otherwise writey *> pure x).
– Jon Purdy
Nov 6 at 0:56
1
1
why is it finite?
– karakfa
Nov 5 at 16:37
why is it finite?
– karakfa
Nov 5 at 16:37
@karakfa We only involve finite lists above.
xs is finite, so inits xs is finite, and >>= loops over a finite number of finite prefixes. mapM loops over each element (finitely many), and replaces them with an element taken from xs (finite).– chi
Nov 5 at 17:07
@karakfa We only involve finite lists above.
xs is finite, so inits xs is finite, and >>= loops over a finite number of finite prefixes. mapM loops over each element (finitely many), and replaces them with an element taken from xs (finite).– chi
Nov 5 at 17:07
1
1
This doesn’t actually use the elements of the results of
inits, just their lengths, so you could write this a bit more explicitly (albeit less elegantly imo) as join [sequence $ take n $ repeat xs | n <- [0..length xs]]. Also it’s worth knowing that mapM (const xs) = sequence . fmap (const xs) = sequence . (xs <$); the expression x <$ y is handy for replacing all elements in the container y with x while retaining its shape, or running an action y, discarding its result, and returning x (where you might otherwise write y *> pure x).– Jon Purdy
Nov 6 at 0:56
This doesn’t actually use the elements of the results of
inits, just their lengths, so you could write this a bit more explicitly (albeit less elegantly imo) as join [sequence $ take n $ repeat xs | n <- [0..length xs]]. Also it’s worth knowing that mapM (const xs) = sequence . fmap (const xs) = sequence . (xs <$); the expression x <$ y is handy for replacing all elements in the container y with x while retaining its shape, or running an action y, discarding its result, and returning x (where you might otherwise write y *> pure x).– Jon Purdy
Nov 6 at 0:56
add a comment |
up vote
2
down vote
Hmm I guess you a need a lazy infinite list of cycling subsequences. One naive way could be like
Prelude> take 100 $ nub . subsequences . cycle $ [2,4,8]
[,[2],[4],[2,4],[8],[2,8],[4,8],[2,4,8],[2,2],[4,2],[2,4,2],[8,2],[2,8,2],[4,8,2],[2,4,8,2],[4,4],[2,4,4],[8,4],[2,8,4],[4,8,4],[2,4,8,4],[2,2,4],[4,2,4],[2,4,2,4],[8,2,4],[2,8,2,4],[4,8,2,4],[2,4,8,2,4],[8,8],[2,8,8],[4,8,8],[2,4,8,8],[2,2,8],[4,2,8],[2,4,2,8],[8,2,8],[2,8,2,8],[4,8,2,8],[2,4,8,2,8],[4,4,8],[2,4,4,8],[8,4,8],[2,8,4,8],[4,8,4,8],[2,4,8,4,8],[2,2,4,8],[4,2,4,8],[2,4,2,4,8],[8,2,4,8],[2,8,2,4,8],[4,8,2,4,8],[2,4,8,2,4,8],[2,2,2],[4,2,2],[2,4,2,2],[8,2,2],[2,8,2,2],[4,8,2,2],[2,4,8,2,2],[4,4,2],[2,4,4,2],[8,4,2],[2,8,4,2],[4,8,4,2],[2,4,8,4,2],[2,2,4,2],[4,2,4,2],[2,4,2,4,2],[8,2,4,2],[2,8,2,4,2],[4,8,2,4,2],[2,4,8,2,4,2]]
answered Nov 5 at 17:16
Redu
12.5k22435
add a comment |
up vote
2
down vote
Hmm I guess you a need a lazy infinite list of cycling subsequences. One naive way could be like
Prelude> take 100 $ nub . subsequences . cycle $ [2,4,8]
[,[2],[4],[2,4],[8],[2,8],[4,8],[2,4,8],[2,2],[4,2],[2,4,2],[8,2],[2,8,2],[4,8,2],[2,4,8,2],[4,4],[2,4,4],[8,4],[2,8,4],[4,8,4],[2,4,8,4],[2,2,4],[4,2,4],[2,4,2,4],[8,2,4],[2,8,2,4],[4,8,2,4],[2,4,8,2,4],[8,8],[2,8,8],[4,8,8],[2,4,8,8],[2,2,8],[4,2,8],[2,4,2,8],[8,2,8],[2,8,2,8],[4,8,2,8],[2,4,8,2,8],[4,4,8],[2,4,4,8],[8,4,8],[2,8,4,8],[4,8,4,8],[2,4,8,4,8],[2,2,4,8],[4,2,4,8],[2,4,2,4,8],[8,2,4,8],[2,8,2,4,8],[4,8,2,4,8],[2,4,8,2,4,8],[2,2,2],[4,2,2],[2,4,2,2],[8,2,2],[2,8,2,2],[4,8,2,2],[2,4,8,2,2],[4,4,2],[2,4,4,2],[8,4,2],[2,8,4,2],[4,8,4,2],[2,4,8,4,2],[2,2,4,2],[4,2,4,2],[2,4,2,4,2],[8,2,4,2],[2,8,2,4,2],[4,8,2,4,2],[2,4,8,2,4,2]]
answered Nov 5 at 17:16
Redu
12.5k22435
add a comment |
up vote
2
down vote
up vote
2
down vote
Hmm I guess you a need a lazy infinite list of cycling subsequences. One naive way could be like
Prelude> take 100 $ nub . subsequences . cycle $ [2,4,8]
[,[2],[4],[2,4],[8],[2,8],[4,8],[2,4,8],[2,2],[4,2],[2,4,2],[8,2],[2,8,2],[4,8,2],[2,4,8,2],[4,4],[2,4,4],[8,4],[2,8,4],[4,8,4],[2,4,8,4],[2,2,4],[4,2,4],[2,4,2,4],[8,2,4],[2,8,2,4],[4,8,2,4],[2,4,8,2,4],[8,8],[2,8,8],[4,8,8],[2,4,8,8],[2,2,8],[4,2,8],[2,4,2,8],[8,2,8],[2,8,2,8],[4,8,2,8],[2,4,8,2,8],[4,4,8],[2,4,4,8],[8,4,8],[2,8,4,8],[4,8,4,8],[2,4,8,4,8],[2,2,4,8],[4,2,4,8],[2,4,2,4,8],[8,2,4,8],[2,8,2,4,8],[4,8,2,4,8],[2,4,8,2,4,8],[2,2,2],[4,2,2],[2,4,2,2],[8,2,2],[2,8,2,2],[4,8,2,2],[2,4,8,2,2],[4,4,2],[2,4,4,2],[8,4,2],[2,8,4,2],[4,8,4,2],[2,4,8,4,2],[2,2,4,2],[4,2,4,2],[2,4,2,4,2],[8,2,4,2],[2,8,2,4,2],[4,8,2,4,2],[2,4,8,2,4,2]]
answered Nov 5 at 17:16
Redu
12.5k22435
Hmm I guess you a need a lazy infinite list of cycling subsequences. One naive way could be like
Prelude> take 100 $ nub . subsequences . cycle $ [2,4,8]
[,[2],[4],[2,4],[8],[2,8],[4,8],[2,4,8],[2,2],[4,2],[2,4,2],[8,2],[2,8,2],[4,8,2],[2,4,8,2],[4,4],[2,4,4],[8,4],[2,8,4],[4,8,4],[2,4,8,4],[2,2,4],[4,2,4],[2,4,2,4],[8,2,4],[2,8,2,4],[4,8,2,4],[2,4,8,2,4],[8,8],[2,8,8],[4,8,8],[2,4,8,8],[2,2,8],[4,2,8],[2,4,2,8],[8,2,8],[2,8,2,8],[4,8,2,8],[2,4,8,2,8],[4,4,8],[2,4,4,8],[8,4,8],[2,8,4,8],[4,8,4,8],[2,4,8,4,8],[2,2,4,8],[4,2,4,8],[2,4,2,4,8],[8,2,4,8],[2,8,2,4,8],[4,8,2,4,8],[2,4,8,2,4,8],[2,2,2],[4,2,2],[2,4,2,2],[8,2,2],[2,8,2,2],[4,8,2,2],[2,4,8,2,2],[4,4,2],[2,4,4,2],[8,4,2],[2,8,4,2],[4,8,4,2],[2,4,8,4,2],[2,2,4,2],[4,2,4,2],[2,4,2,4,2],[8,2,4,2],[2,8,2,4,2],[4,8,2,4,2],[2,4,8,2,4,2]]
answered Nov 5 at 17:16
Redu
12.5k22435
answered Nov 5 at 17:16
Redu
12.5k22435
answered Nov 5 at 17:16
Redu
12.5k22435
answered Nov 5 at 17:16
Redu
12.5k22435
12.5k22435
add a comment |
add a comment |
up vote
0
down vote
This produces the elements in a different order within each length than your example, but it meets the definition of the text of your question. Changing the order is easy - you have to replace <*> with a slightly different operator of your own making.
import Control.Applicative
import Control.Monad
rinvjoin :: Applicative both => both a -> both (both a)
rinvjoin = fmap pure
extendBranches options branches = (<|>) <$> options <*> branches
singletonBranchExtensions = rinvjoin
genAllSize =
genAllSize xs = join <$> iterate (extendBranches extensions) $ initialBranches
where extensions = singletonBranchExtensions xs
initialBranches = pure empty
answered Nov 11 at 10:37
codeshot
7231718
indeed. But I'm going to leave it because I get confused by the myriad of maximally refined concepts and I bet others do too.
– codeshot
Nov 11 at 11:06
My current solution has a problem that it keeps looking for branch extensions forever for genAllSize but where there's a finite answer, the list should be finite, really
– codeshot
Nov 11 at 11:07
genAllSize xs = join $ iterate (liftA2 (<|>) (pure <$> xs)) (pure empty)is write-only, though. Mine needs to be expanded out into more explicit definitions as it is, removing some can't be right.
– codeshot
Nov 11 at 11:09
It's not supposed to do what chi's answer is doing, chi's answer isn't correct
– codeshot
Nov 11 at 11:13
[2,2,2,2] is a list made from some combination of elements from [2,4,8] and yet chi's answer doesn't include it in the output list. My answer correctly includes it.
– codeshot
Nov 11 at 11:22
|
show 5 more comments
up vote
0
down vote
This produces the elements in a different order within each length than your example, but it meets the definition of the text of your question. Changing the order is easy - you have to replace <*> with a slightly different operator of your own making.
import Control.Applicative
import Control.Monad
rinvjoin :: Applicative both => both a -> both (both a)
rinvjoin = fmap pure
extendBranches options branches = (<|>) <$> options <*> branches
singletonBranchExtensions = rinvjoin
genAllSize =
genAllSize xs = join <$> iterate (extendBranches extensions) $ initialBranches
where extensions = singletonBranchExtensions xs
initialBranches = pure empty
answered Nov 11 at 10:37
codeshot
7231718
indeed. But I'm going to leave it because I get confused by the myriad of maximally refined concepts and I bet others do too.
– codeshot
Nov 11 at 11:06
My current solution has a problem that it keeps looking for branch extensions forever for genAllSize but where there's a finite answer, the list should be finite, really
– codeshot
Nov 11 at 11:07
genAllSize xs = join $ iterate (liftA2 (<|>) (pure <$> xs)) (pure empty)is write-only, though. Mine needs to be expanded out into more explicit definitions as it is, removing some can't be right.
– codeshot
Nov 11 at 11:09
It's not supposed to do what chi's answer is doing, chi's answer isn't correct
– codeshot
Nov 11 at 11:13
[2,2,2,2] is a list made from some combination of elements from [2,4,8] and yet chi's answer doesn't include it in the output list. My answer correctly includes it.
– codeshot
Nov 11 at 11:22
|
show 5 more comments
up vote
0
down vote
up vote
0
down vote
This produces the elements in a different order within each length than your example, but it meets the definition of the text of your question. Changing the order is easy - you have to replace <*> with a slightly different operator of your own making.
import Control.Applicative
import Control.Monad
rinvjoin :: Applicative both => both a -> both (both a)
rinvjoin = fmap pure
extendBranches options branches = (<|>) <$> options <*> branches
singletonBranchExtensions = rinvjoin
genAllSize =
genAllSize xs = join <$> iterate (extendBranches extensions) $ initialBranches
where extensions = singletonBranchExtensions xs
initialBranches = pure empty
answered Nov 11 at 10:37
codeshot
7231718
This produces the elements in a different order within each length than your example, but it meets the definition of the text of your question. Changing the order is easy - you have to replace <*> with a slightly different operator of your own making.
import Control.Applicative
import Control.Monad
rinvjoin :: Applicative both => both a -> both (both a)
rinvjoin = fmap pure
extendBranches options branches = (<|>) <$> options <*> branches
singletonBranchExtensions = rinvjoin
genAllSize =
genAllSize xs = join <$> iterate (extendBranches extensions) $ initialBranches
where extensions = singletonBranchExtensions xs
initialBranches = pure empty
answered Nov 11 at 10:37
codeshot
7231718
edited Nov 11 at 11:30
answered Nov 11 at 10:37
codeshot
7231718
answered Nov 11 at 10:37
codeshot
7231718
answered Nov 11 at 10:37
codeshot
7231718
7231718
indeed. But I'm going to leave it because I get confused by the myriad of maximally refined concepts and I bet others do too.
– codeshot
Nov 11 at 11:06
My current solution has a problem that it keeps looking for branch extensions forever for genAllSize but where there's a finite answer, the list should be finite, really
– codeshot
Nov 11 at 11:07
genAllSize xs = join $ iterate (liftA2 (<|>) (pure <$> xs)) (pure empty)is write-only, though. Mine needs to be expanded out into more explicit definitions as it is, removing some can't be right.
– codeshot
Nov 11 at 11:09
It's not supposed to do what chi's answer is doing, chi's answer isn't correct
– codeshot
Nov 11 at 11:13
[2,2,2,2] is a list made from some combination of elements from [2,4,8] and yet chi's answer doesn't include it in the output list. My answer correctly includes it.
– codeshot
Nov 11 at 11:22
|
show 5 more comments
indeed. But I'm going to leave it because I get confused by the myriad of maximally refined concepts and I bet others do too.
– codeshot
Nov 11 at 11:06
My current solution has a problem that it keeps looking for branch extensions forever for genAllSize but where there's a finite answer, the list should be finite, really
– codeshot
Nov 11 at 11:07
genAllSize xs = join $ iterate (liftA2 (<|>) (pure <$> xs)) (pure empty)is write-only, though. Mine needs to be expanded out into more explicit definitions as it is, removing some can't be right.
– codeshot
Nov 11 at 11:09
It's not supposed to do what chi's answer is doing, chi's answer isn't correct
– codeshot
Nov 11 at 11:13
[2,2,2,2] is a list made from some combination of elements from [2,4,8] and yet chi's answer doesn't include it in the output list. My answer correctly includes it.
– codeshot
Nov 11 at 11:22
indeed. But I'm going to leave it because I get confused by the myriad of maximally refined concepts and I bet others do too.
– codeshot
Nov 11 at 11:06
indeed. But I'm going to leave it because I get confused by the myriad of maximally refined concepts and I bet others do too.
– codeshot
Nov 11 at 11:06
My current solution has a problem that it keeps looking for branch extensions forever for genAllSize but where there's a finite answer, the list should be finite, really
– codeshot
Nov 11 at 11:07
My current solution has a problem that it keeps looking for branch extensions forever for genAllSize but where there's a finite answer, the list should be finite, really
– codeshot
Nov 11 at 11:07
genAllSize xs = join $ iterate (liftA2 (<|>) (pure <$> xs)) (pure empty) is write-only, though. Mine needs to be expanded out into more explicit definitions as it is, removing some can't be right.– codeshot
Nov 11 at 11:09
genAllSize xs = join $ iterate (liftA2 (<|>) (pure <$> xs)) (pure empty) is write-only, though. Mine needs to be expanded out into more explicit definitions as it is, removing some can't be right.– codeshot
Nov 11 at 11:09
It's not supposed to do what chi's answer is doing, chi's answer isn't correct
– codeshot
Nov 11 at 11:13
It's not supposed to do what chi's answer is doing, chi's answer isn't correct
– codeshot
Nov 11 at 11:13
[2,2,2,2] is a list made from some combination of elements from [2,4,8] and yet chi's answer doesn't include it in the output list. My answer correctly includes it.
– codeshot
Nov 11 at 11:22
[2,2,2,2] is a list made from some combination of elements from [2,4,8] and yet chi's answer doesn't include it in the output list. My answer correctly includes it.
– codeshot
Nov 11 at 11:22
|
show 5 more comments
draft saved
draft discarded
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53157534%2fgenerate-all-permutations-of-a-list-including-diferent-sizes-and-repeated-elemen%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
filterM (_ -> [False, True]) [2,4,8]– Willem Van Onsem
Nov 5 at 15:44
@WillemVanOnsem That doesn't select with replacement.
– chepner
Nov 5 at 15:46
@chepner: aarghh, I missed that part :(
– Willem Van Onsem
Nov 5 at 15:48
That solution does not take in account the possibility of repeated numbers. I did not want to post my solution because it was pretty ugly tho... I even came up with a solution without permutations and it's pretty ugly too
– Adrià Cabeza Sant'Anna
Nov 5 at 16:07
genAllSize x = concat(iterate (z -> genAllSize' z x) []) where genAllSize' l li = foldl (t i -> t++(map(s -> s++[i]) l ) ) [ ] li– Adrià Cabeza Sant'Anna
Nov 5 at 16:09