Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #80365 > unrolled thread

generating 2D bit array variants with specific algorythm

Back to article view | Back to comp.lang.python

Contents

  generating 2D bit array variants with specific algorythm Robert Voigtländer <r.voigtlaender@gmail.com> - 2014-11-07 07:39 -0800
    Re: generating 2D bit array variants with specific algorythm Joel Goldstick <joel.goldstick@gmail.com> - 2014-11-07 10:51 -0500
      Re: generating 2D bit array variants with specific algorythm Robert Voigtländer <r.voigtlaender@gmail.com> - 2014-11-07 08:02 -0800
        Re: generating 2D bit array variants with specific algorythm "ast" <nomail@invalid.com> - 2014-11-07 17:40 +0100
    Re: generating 2D bit array variants with specific algorythm Peter Otten <__peter__@web.de> - 2014-11-07 17:29 +0100
    Re: generating 2D bit array variants with specific algorythm "ast" <nomail@invalid.com> - 2014-11-07 17:57 +0100
      Re: generating 2D bit array variants with specific algorythm "ast" <nomail@invalid.com> - 2014-11-07 17:58 +0100
    Re:generating 2D bit array variants with specific algorythm Dave Angel <davea@davea.name> - 2014-11-07 14:34 -0500
    Re: generating 2D bit array variants with specific algorythm Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2014-11-07 15:41 -0500
    Re: generating 2D bit array variants with specific algorythm Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-11-08 10:13 +1300
      Re: generating 2D bit array variants with specific algorythm sohcahtoa82@gmail.com - 2014-11-07 17:10 -0800

#80365 — generating 2D bit array variants with specific algorythm

Hi,

I need to generate all variants of a 2D array with variable dimension sizes which fit a specific rule. (up to 200*1000)

The rules are:
- Values are only 0 or 1
- the sum of each line bust be 1
- only valid results must be generated (generating all and only returning the valid results takes to long; that's what I tried already)

So for a 2x2 array these would be the valid results:

10
01

01
10

10
10

01
01


Must be possible with nested loops and a counter per line. But I don't get it.

Can someone help?

Thanks
Robert

[toc] | [next] | [standalone]

#80368

On Fri, Nov 7, 2014 at 10:39 AM, Robert Voigtländer
<r.voigtlaender@gmail.com> wrote:
> Hi,
>
> I need to generate all variants of a 2D array with variable dimension sizes which fit a specific rule. (up to 200*1000)
>
> The rules are:
> - Values are only 0 or 1
> - the sum of each line bust be 1
> - only valid results must be generated (generating all and only returning the valid results takes to long; that's what I tried already)
>
> So for a 2x2 array these would be the valid results:
>
> 10
> 01
>
> 01
> 10
>
> 10
> 10
>
> 01
> 01
>
>
> Must be possible with nested loops and a counter per line. But I don't get it.
>
> Can someone help?

is this valid:
1011
What I mean is do you throw away the carry or does each row have only one zero?

>
> Thanks
> Robert
> --
> https://mail.python.org/mailman/listinfo/python-list



-- 
Joel Goldstick
http://joelgoldstick.com

[toc] | [prev] | [next] | [standalone]

#80369

> 1011
> What I mean is do you throw away the carry or does each row have only one zero?

Not sure what you mean. Each row must have one 1. The rest must be 0.
No combinations not fitting this rule must be generated.

[toc] | [prev] | [next] | [standalone]

#80372

"Robert Voigtländer" <r.voigtlaender@gmail.com> a écrit dans le message de 
news:e5c93b46-a32b-4eca-a00d-f7dd2b4bb8ee@googlegroups.com...
>> 1011
>> What I mean is do you throw away the carry or does each row have only one zero?
>
> Not sure what you mean. Each row must have one 1. The rest must be 0.
> No combinations not fitting this rule must be generated.

OK exactly one 1 per line, others are 0
I understood sum modulo 2 = 1, so an odd number of 1 as joel ;) 

[toc] | [prev] | [next] | [standalone]

#80371

Robert Voigtländer wrote:

> Hi,
> 
> I need to generate all variants of a 2D array with variable dimension
> sizes which fit a specific rule. (up to 200*1000)
> 
> The rules are:
> - Values are only 0 or 1
> - the sum of each line bust be 1
> - only valid results must be generated (generating all and only returning
> the valid results takes to long; that's what I tried already)
> 
> So for a 2x2 array these would be the valid results:
> 
> 10
> 01
> 
> 01
> 10
> 
> 10
> 10
> 
> 01
> 01
> 
> 
> Must be possible with nested loops and a counter per line. But I don't get
> it.
> 
> Can someone help?

Have a look at itertools.product(). If you need to code it in Python -- the 
documentation has an example implementation.

from itertools import product

def f(n):
    rows = [[0] * n for i in range(n)]
    for i, row in enumerate(rows):
        row[i] = 1
    rows = [tuple(row) for row in rows]
    return list(product(rows, repeat=n))

if __name__ == "__main__":
    from pprint import pprint
    pprint(f(2))
    print("---")
    pprint(f(3))

However, n**n is growing quite fast; you'll soon reach the limits of what is 
feasible in Python. Maybe numpy has something to offer to push these limits 
a bit. An optimisation would be to store the position of the 1, i. e.

01

10

00

11

for n=2. If you reorder these you get 0, 1, 2, 3. I think I'm seeing a 
pattern...

[toc] | [prev] | [next] | [standalone]

#80373

"Robert Voigtländer" <r.voigtlaender@gmail.com> a écrit dans le message de 
news:0e6787f9-88d6-423a-8410-7578fa83d61c@googlegroups.com...

Let be L the number of lines and C the numbers of column

You solve your problem just with counting on base C

On base C, a number may be represented with

N(L-1)N(L-2) ... N(0)N(0) where N(i) goes from 0 to C-1

N(i) is associated with line i of your array. Lines are numbered from 0
if N(i) == j, then bit in column j of line i is 1 and all others 0, columns are numbered from 0

For example, with an array of 2 lines and 3 colums

00 -->

100 <  line 1
100  < line 0

01 ->

100
010

02 ->

100
001

10 ->

010
100

11 ->

010
010

12 ->

010
001

20 ->

001
100

21 ->

001
010

22 ->

001
001

[toc] | [prev] | [next] | [standalone]

#80374

"ast" <nomail@invalid.com> a écrit dans le message de news:545cf9f0$0$2913$426a34cc@news.free.fr...

> On base C, a number may be represented with
>
> N(L-1)N(L-2) ... N(1)N(0) where N(i) goes from 0 to C-1

[toc] | [prev] | [next] | [standalone]

#80379

Robert Voigtländer <r.voigtlaender@gmail.com> Wrote in message:
> Hi,
> 
> I need to generate all variants of a 2D array with variable dimension sizes which fit a specific rule. (up to 200*1000)
> 
> The rules are:
> - Values are only 0 or 1
> - the sum of each line bust be 1
> - only valid results must be generated (generating all and only returning the valid results takes to long; that's what I tried already)
> 
> So for a 2x2 array these would be the valid results:
> 
> 10
> 01
> 
> 01
> 10
> 
> 10
> 10
> 
> 01
> 01
> 
> 
> Must be possible with nested loops and a counter per line. But I don't get it.

If the matrix is m by n, then there are 2**n possibilities for
 each row. But only n of them are legal by your rules. So your
 problem is just a matter of counting in base n, all the possible
 m digit numbers.


-- 
DaveA

[toc] | [prev] | [next] | [standalone]

#80381

On Fri, 7 Nov 2014 07:39:27 -0800 (PST), Robert Voigtländer
<r.voigtlaender@gmail.com> declaimed the following:

>Hi,
>
>I need to generate all variants of a 2D array with variable dimension sizes which fit a specific rule. (up to 200*1000)
>
>The rules are:
>- Values are only 0 or 1
>- the sum of each line bust be 1

	This criteria means that there can be only ONE 1 per line, and there
must be ONE 1 per line

>- only valid results must be generated (generating all and only returning the valid results takes to long; that's what I tried already)

	Given the rephrased criteria -- then ALL results are valid as you
should never even consider generating a line that has none, or more than
one, 1 in it.

	Initialize each line as

	aLine = "0" * (width - 1) + "1"

>
>Must be possible with nested loops and a counter per line. But I don't get it.
>

	From there, you just need to rotate by one character the first line...
When the 1 rotates off the left, you have to rotate the next line by one
character, and go back to the start... repeat as needed until the last line
has rotated around.

	Of course, this is perhaps the harder way to implement it... Might be
easier to just keep a list of the current 1 position on each line,
increment it until it reaches the maximum width, then carry to the next
line... And only produce the actual data as output...

-=-=-=-=-=-=-=-
pynff MrebBar(bowrpg):
    qrs __vavg__(frys, jvqgu=2, urvtug=2):
        frys._zngevk = [ 0 sbe y va enatr(urvtug) ]
        frys._jvqgu = jvqgu
        frys._urvtug = urvtug
    qrs qvfcynl(frys):
        cevag "*" * frys._jvqgu
        sbe y va enatr(frys._urvtug):
            ya = ["0"] * frys._jvqgu
            ya[frys._zngevk[y]] = "1"
            cevag "".wbva(ya)
        cevag "*" * frys._jvqgu
    qrs arkg(frys):
        sbe ya va enatr(frys._urvtug):
            pneel = frys._ebgngr(ya)
            vs abg pneel: oernx
            vs ya == frys._urvtug - 1: erghea Gehr  
								#pneel ba ynfg yvar, qbar
        erghea Snyfr
    qrs _ebgngr(frys, ya):
        frys._zngevk[ya] += 1
        pneel = Snyfr
        vs frys._zngevk[ya] == frys._jvqgu:
            frys._zngevk[ya] = 0
            pneel = Gehr
        erghea pneel

vs __anzr__ == "__znva__":
    qrsnhyg = MrebBar()
    qrsnhyg.qvfcynl()
    juvyr Gehr:
        vs qrsnhyg.arkg(): oernx
        qrsnhyg.qvfcynl()

    bgure = MrebBar(4, 6)
    bgure.qvfcynl()
    juvyr Gehr:
        vs bgure.arkg(): oernx
        bgure.qvfcynl()
-=-=-=-=-=-=-=-=-
    
	Now -- if the real criteria is that the sum of each row AND the sum of
each column must be 1, that is a more difficult problem; but your example
2x2 does not seem to mandate that.

-- 
	Wulfraed                 Dennis Lee Bieber         AF6VN
    wlfraed@ix.netcom.com    HTTP://wlfraed.home.netcom.com/

[toc] | [prev] | [next] | [standalone]

#80383

Robert Voigtländer wrote:

> I need to generate all variants of a 2D array with variable dimension sizes
> which fit a specific rule. (up to 200*1000)

Um... you realise there are 200**1000 solutions for the
200x1000 case? Are you sure that's really what you want?

-- 
Greg

[toc] | [prev] | [next] | [standalone]

#80389

On Friday, November 7, 2014 1:13:27 PM UTC-8, Gregory Ewing wrote:
> Robert Voigtländer wrote:
> 
> > I need to generate all variants of a 2D array with variable dimension sizes
> > which fit a specific rule. (up to 200*1000)
> 
> Um... you realise there are 200**1000 solutions for the
> 200x1000 case? Are you sure that's really what you want?
> 
> -- 
> Greg


It sounds like it is indeed what he wants, however, this is likely a homework assignment and the idea is that your program COULD produce the answer for that if he wanted, not that he will actually be using the result.

I'd handle it with recursion, myself.  It sounds like a cool idea for a game of Code Golf on Stack Exchange.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web