Paste: Combinations

Author: Loryn Jenkins
Mode: factor
Date: Fri, 29 Mar 2013 00:46:23
Plain Text | 
I've written I word, combinations, which takes a sequence:
{ "a" "b" "c" "d" }

and emits a sequence where each term is combined with each other term:
{ { "a" "b" } { "a" "c" } { "a" "d" } { "b" "c" } { "b" "d" } { "c" "d" } }

When I was writing it, I was trying to write it in a functional style. But it hasn't turned out so functional. I figure I'm missing a number of abstractions or approaches to doing this in a functional style.


USING: kernel make sequences arrays prettyprint ;
IN: combinations

: make-pairs ( seq seq -- seq )
    [ [ [ , , ] { } make , ] cartesian-each ] { } make ;

: combine ( seq -- seq seq )
    1 cut* over make-pairs ;

: process ( seq seq -- seq seq )
    dup length 1 = [ ] [ combine swap [ append! ] dip process ] if ;         
   
: combinations ( seq -- seq )
    V{ } clone swap process drop ;

Annotation: Revised version

Author: Loryn Jenkins
Mode: factor
Date: Fri, 29 Mar 2013 06:22:10
Plain Text | 
After reviewing this code with #concatenative's RodgerTheGreat, this is what I've ended up with.

! Copyright (C) 2013 Loryn Jenkins.
! See http://factorcode.org/license.txt for BSD license.
USING: kernel make shuffle sequences prettyprint ;

IN: combinations

: make-pairs ( seq1 seq2 -- seq-pairs )
    [ [ [ swap , , ] { } make , ] cartesian-each ] { } make ;
  
: slice-and-dice ( seq -- head-pair-seq tail-seq )
    1 cut tuck make-pairs swap ;
    
: process ( acc seq -- acc' seq' )
    [ dup length 1 = ] [ slice-and-dice [ append! ] dip process ] until ;                  
   
: combinations ( seq -- seq )
    V{ } clone swap process drop ;

: combinations. ( seq -- )
    combinations . ;


Still, for the life of me, don't know why the unit tests aren't working though. Interactive testing in the listener shows that the code is working: but the unit tests are failing.

! Copyright (C) 2013 Loryn Jenkins.
! See http://factorcode.org/license.txt for BSD license.
USING: tools.test combinations sets ;
IN: combinations.tests

: push-abcd ( -- seq )    
    { "a" "b" "c" "d" } ;
    
: push-ints ( -- seq )
    { 1 2 3 4 } ;


{ { "a" "b" } { "a" "c" } { "a" "d" } { "b" "c" } { "b" "d" } { "c" "d" } } 
[ { "a" "b" "c" "d" } combinations ] unit-test

{ { 1 2 } { 1 3 } { 1 4 } { 2 3 } { 2 4 } { 3 4 } } 
[ { 1 2 3 4 } combinations ] unit-test

Annotation: swip combinator

Author: Loryn Jenkins
Mode: factor
Date: Fri, 29 Mar 2013 06:33:30
Plain Text | 
While reviewing the above code, I wrote a combinator to implement the pattern: swap [ quot ] dip

This allows for:
x y z --> x z [ quot ] call y --> x' y


! Copyright (C) 2013 Loryn Jenkins.
! See http://factorcode.org/license.txt for BSD license.
USING: kernel shuffle sequences ;

IN: kernel

: swip ( x y z -- x' y ) [ swapd ] dip call swap ; inline

IN: sequences

: append-back-over! ( x y z -- x-z-append! y ) [ append! ] swip ;
: append-back-over ( x y z -- x-z-append y ) [ append ] swip ;

However, subsequent editing of the program showed that this wasn't necessary. So, swip ended up the offcuts bin.

New Annotation

Summary:
Author:
Mode:
Body: