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 -- https://mail.python.org/mailman/listinfo/python-list
Re: generating 2D bit array variants with specific algorythm
On Fri, Nov 7, 2014 at 10:39 AM, Robert Voigtländer r.voigtlaen...@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 -- https://mail.python.org/mailman/listinfo/python-list
Re: generating 2D bit array variants with specific algorythm
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. -- https://mail.python.org/mailman/listinfo/python-list
Re: generating 2D bit array variants with specific algorythm
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... -- https://mail.python.org/mailman/listinfo/python-list
Re: generating 2D bit array variants with specific algorythm
Robert Voigtländer r.voigtlaen...@gmail.com a écrit dans le message de news:e5c93b46-a32b-4eca-a00d-f7dd2b4bb...@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 ;) -- https://mail.python.org/mailman/listinfo/python-list
Re: generating 2D bit array variants with specific algorythm
Robert Voigtländer r.voigtlaen...@gmail.com a écrit dans le message de news:0e6787f9-88d6-423a-8410-7578fa83d...@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 -- https://mail.python.org/mailman/listinfo/python-list
Re: generating 2D bit array variants with specific algorythm
ast nom...@invalid.com a écrit dans le message de news:545cf9f0$0$2913$426a3...@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 -- https://mail.python.org/mailman/listinfo/python-list
Re: generating 2D bit array variants with specific algorythm
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 -- https://mail.python.org/mailman/listinfo/python-list
Re: generating 2D bit array variants with specific algorythm
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. -- https://mail.python.org/mailman/listinfo/python-list