Prelude> let a = "ABCDE" in [ (x,y) | x <- a, y <- a, x < y ]
[('A','B'),('A','C'),('A','D'),('A','E'),('B','C'),('B','D'),('B','E'),('C','D'),('C','E'),('D','E')]
>>13
Oh, you don't know the difference between permutation and combination?
If you're pursuing a CS degree, change your school. If you're a self-learner, study combinatorics.
An array of five elements, print all unordered pairs?
Simple, consider this in my made up language: x: array <- {a, b, c, d, e}
stdout <- string <- {x->1 x->2,
x->1 x->3,
x->1 x->4,
x->1 x->5,
x->2 x->3,
x->2 x->4,
x->2 x->5,
x->3 x->4,
x->2 x->5,
x->4 x->5}
No need for loops when you know the array size.
>>26
No dumb shit, I wanted to know whether or not OP was asking for combinations or permutations, because I didn't read his list of required outputs. However after reading the list it is obvious that he is looking for all combinations with two indices.
You seem to be confused. In a permutation order matters, in a combination order does not. Try and think before speaking you mental midget.
Name:
Anonymous2012-02-06 0:16
Here's a cartesian product:
#!/usr/bin/lua
local tab = {}
function tab.for_all_values(A, operator)
for _, v in pairs(A) do
operator(v)
end
end
function tab.values_iterator(A)
return coroutine.wrap(function()
tab.for_all_values(A, coroutine.yield)
end)
end
function tab.values_iterator_generator(A)
return function()
return tab.values_iterator(A)
end
end
local iter = {}
function iter.for_all(iterator, operator)
for v in iterator do
operator(v)
end
end
function iter.list(...)
return tab.values_iterator({...})
end
-- iterator is an iterator of iterators
function iter.concat(iterator)
return coroutine.wrap(function()
iter.for_all(iterator,
function(sub_iterator)
iter.for_all(sub_iterator, coroutine.yield)
end)
end)
end
function compose(f, g)
return function(x)
return f(g(x))
end
end
function iter.map1(iterator, operator)
return coroutine.wrap(function()
iter.for_all(iterator, compose(coroutine.yield, operator))
end)
end
function iter.product(iterator1, iterator2_gen)
return iter.concat(iter.map1(iterator1,
function(iterator1_value)
return iter.map1(iterator2_gen(),
function(iterator2_value)
return {iterator1_value, iterator2_value}
end)
end))
end
print"test tab.values_iterator:"
i = tab.values_iterator(A)
for v in i do
print(v)
end
print"test tab.values_iterator_generator:"
g1 = tab.values_iterator_generator(A)
i1 = g1()
for v1 in i1 do
i2 = g1()
for v2 in i2 do
print(v1, v2)
end
end
test tab.for_all_values:
A
B
C
D
E
test tab.values_iterator:
A
B
C
D
E
test tab.values_iterator_generator:
A A
A B
A C
A D
A E
B A
B B
B C
B D
B E
C A
C B
C C
C D
C E
D A
D B
D C
D D
D E
E A
E B
E C
E D
E E
test iter.for_all:
A
B
C
D
E
test iter.list:
hi
there
how
are
you
doing
today?
test iter.concat:
1
2
3
4
5
6
test iter.map1:
3
6
9
12
test iter.product:
A A
A B
A C
A D
A E
B A
B B
B C
B D
B E
C A
C B
C C
C D
C E
D A
D B
D C
D D
D E
E A
E B
E C
E D
E E
Name:
Anonymous2012-02-06 3:35
All n combinations from a list, in 6 lines of scheme:
(define (combinations n lis output)
(cond ((= n 0)
(output '()))
((not (null? lis))
(begin (combinations (- n 1) (cdr lis) (lambda (x) (output (cons (car lis) x))))
(combinations n (cdr lis) output)))))
(combinations 3 '(a b c d e f g) (lambda (x) (display x) (newline)))
:w !scm
#<unspecified>
(a b c)
(a b d)
(a b e)
(a b f)
(a b g)
(a c d)
(a c e)
(a c f)
(a c g)
(a d e)
(a d f)
(a d g)
(a e f)
(a e g)
(a f g)
(b c d)
(b c e)
(b c f)
(b c g)
(b d e)
(b d f)
(b d g)
(b e f)
(b e g)
(b f g)
(c d e)
(c d f)
(c d g)
(c e f)
(c e g)
(c f g)
(d e f)
(d e g)
(d f g)
(e f g)
#<unspecified>
by the way, did you know that you can pipe the content of a file being editted in vim to a command using:
:w !command
It's rather nifty when writing scripts.
Name:
Anonymous2012-02-06 5:21
>>34
I don't like your implementation, your use of lambda is most unusual.
yeah, it functions as a call back. It would be tricky to get it to extract a list, and it would require mutations. But it is trivial in languages that have message passing between threads, and the elements can be extracted lazily.
Here's a more normal functional way of writing it:
(define (combinations n lis)
(cond ((= n 0)
(list '())) ;; The empty set is a zero element subset of any set
((null? lis)
(list)) ;; There are no non empty subsets of the empty set.
(else
(append (map (lambda (rest) (cons (car lis) rest))
(combinations (- n 1) (cdr lis)))
(combinations n (cdr lis))))))
(display (combinations 3 '(a b c d e f g)))
:w !scm
#<unspecified>
((a b c) (a b d) (a b e) (a b f) (a b g) (a c d) (a c e) (a c f) (a c g) (a d e) (a d f) (a d g) (a e f) (a e g) (a f g) (b c d) (b c e) (b c f) (b c g) (b d e) (b d f) (b d g) (b e f) (b e g) (b f g) (c d e) (c d f) (c d g) (c e f) (c e g) (c f g) (d e f) (d e g) (d f g) (e f g))#<unspecified>
The appends could be inefficient though.
Name:
Anonymous2012-02-06 6:49
my_list = ['a', 'b','c', 'd', 'e']
for i in my_list:
for j in my_list:
print(i, j)
>>32
>No dumb shit, I wanted to know whether or not OP was asking >for combinations or permutations, because I didn't read his >list of required outputs. However after reading the list it is >obvious that he is looking for all combinations with two >indices.
It's kind of funny how everyone, except for you, thought it was a permutation.
>You seem to be confused. In a permutation order matters, in a >combination order does not. Try and think before speaking you >mental midget.
Stop projecting. I was able to post working code that produced the correct output you didn't.
>>32
[quote]
No dumb shit, I wanted to know whether or not OP was asking for combinations or permutations, because I didn't read his list of required outputs. However after reading the list it is obvious that he is looking for all combinations with two indices.
[/quote]
It's kind of funny how everyone, except for you, thought it was a permutation.
[quote]
You seem to be confused. In a permutation order matters, in a combination order does not. Try and think before speaking you mental midget.
[/quote]
Stop projecting. I was able to post working code that produced the correct output. You didn't. Presumably because you are a clueless twat that doesn't have an ounce of programmers blood in them.
Name:
Anonymous2012-02-06 10:29
>>43
I swear this is the special olypmics of computer programmin. In on corner we have the homo who can't come up with a correct programming solution. In the other corner we have the minimum wage toilet scrubber who doesn't seem to understand the difference between a combination and a permutation.
Name:
Anonymous2012-02-06 10:30
>>45
And apparently I can't type for shit this morning.
Name:
Anonymous2012-02-07 7:33
This one might be more efficient than the binary recursive one. It still has an append though. And the sets are backwards, and it needs a cut off number for the size of the lists. It calculates each subset of n elements, giving it a best case running time of 2^n,
(define (combinations lis)
(letrec ((helper (lambda (lis accumulation)
(if (null? lis)
accumulation
(helper (cdr lis)
(append accumulation
(map (lambda (rest) (cons (car lis) rest))
accumulation)))))))
(helper lis (list '())))) ;; start with the empty set in accumulation
(combinations '(a b c d e))
:w !scm
#<unspecified>
(() (a) (b) (b a) (c) (c a) (c b) (c b a) (d) (d a) (d b) (d b a) (d c) (d c a) (d c b) (d c b a) (e) (e a) (e b) (e b a) (e c) (e c a) (e c b) (e c b a) (e d) (e d a) (e d b) (e d b a) (e d c) (e d c a) (e d c b) (e d c b a))
Name:
Anonymous2012-02-07 8:02
A zomg optimized version that avoids using append, but the ordering of the results becomes very strange. There's a lot of reused memory here. IE, (e c b) and (d c b) have the same cdr.
:w !scm
#<unspecified>
((e) (e a) (e b a) (e b) (e c b) (e c b a) (e c a) (e c) (e d c) (e d c a) (e d c b a) (e d c b) (e d b) (e d b a) (e d a) (e d) (d) (d a) (d b a) (d b) (d c b) (d c b a) (d c a) (d c) (c) (c a) (c b a) (c b) (b) (b a) (a) ())
Name:
Anonymous2012-02-07 8:42
So why aren't your solutions as easy as >>8?
I mean if your language is going to be slow as shit it might as well offer the things that Python offer.
>>51
I should have looked up what permutations() did in python. My apologies, I assumed it would be consistent with the mathematical definition. How foolish of me.