1. Forum
  2. Usenet
  3. COMP.LANG.AWK

  • subsets of an array

    From Janis Papanagnou@21:1/5 to Tim Menzies on Tue Mar 23 00:45:06 2021
    On 22.03.2021 23:14, Tim Menzies wrote:
    given an array a[1]=10,a[2]=20,a[3]=30 anyone got an iterator that runs over all subsets. for example:

    function show(lst) { print ""; for(i in lst ) print(i,lst[i]) }

    forsubs("show", a) ==>

    10

    20

    30

    40

    10, 20

    10,30

    20,30

    10,20,30

    (I suppose the "40" was a typo?)

    As for a solution, with GNU awk where I can use bit-operations,
    I might implement something like

    function forsubs (a, n, m, z, w) {
    n=length(a)
    m=2^n
    for (z=1; z<m; z++) {
    w=1
    for (y=1; y<m; y*=2) {
    if (and(z,y)) printf " %s", a[w]
    w++
    }
    printf "\n"
    }
    }
    BEGIN { a[1]=10 ; a[2]=20 ; a[3]=30 ; forsubs(a) }

    to create this output

    10
    20
    10 20
    30
    10 30
    20 30
    10 20 30

    The function relies on some properties (e.g. contiguous indices in a),
    and to define another order of the resulting permutation you need some
    tweaks.

    Janis

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Kaz Kylheku@21:1/5 to Tim Menzies on Mon Mar 22 23:55:08 2021
    On 2021-03-22, Tim Menzies <timm@ieee.org> wrote:
    given an array a[1]=10,a[2]=20,a[3]=30 anyone got an iterator that runs over all subsets. for example:

    The set of all subsets is the "power set". Is that what you mean?

    The Rosetta Code site has solutions for calculating the power set in (at
    the time of writing) 96 languages, including Awk

    http://rosettacode.org/wiki/Power_Set#AWK

    10

    20

    30

    40

    10, 20

    10,30

    20,30

    10,20,30

    The Rosetta Awk solution doesn't walk the subsets in this order,
    unfortunately; if you need that, you have work to do.

    --
    TXR Programming Language: http://nongnu.org/txr
    Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From J Naman@21:1/5 to ti...@ieee.org on Mon Mar 22 17:32:44 2021
    On Monday, 22 March 2021 at 18:14:59 UTC-4, ti...@ieee.org wrote:
    given an array a[1]=10,a[2]=20,a[3]=30 anyone got an iterator that runs over all subsets. for example:

    function show(lst) { print ""; for(i in lst ) print(i,lst[i]) }

    forsubs("show", a) ==>

    10

    20

    30

    40

    10, 20

    10,30

    20,30

    10,20,30
    Two fun algorithms, given in C, C++, etc. Easy to Gawk.
    iterative, using bits to filter output subsets, easy on memory https://www.geeksforgeeks.org/power-set/

    recursive, 2^nth deep. Watch memory! https://www.geeksforgeeks.org/backtracking-to-find-all-subsets/

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Tim Menzies@21:1/5 to All on Mon Mar 22 15:14:58 2021
    given an array a[1]=10,a[2]=20,a[3]=30 anyone got an iterator that runs over all subsets. for example:

    function show(lst) { print ""; for(i in lst ) print(i,lst[i]) }

    forsubs("show", a) ==>

    10

    20

    30

    40

    10, 20

    10,30

    20,30

    10,20,30

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)