shifter of multiple elements in 2-dimensional array in Python-CodePudding

in Python, let's suppose I have 4x13 list. Inside this list, values on first seven positions are 1, while values at the rest of the positions are 0. List basically represents pack of cards, when 1 means we picked one specific card, and 0 means we did not. Now I need to gradually "shift" 1s inside the list, to go through all possible states of the list (there are C(7)52 = 133 milions of possible states).

I have writen this code below, which represents shifting of 2 cards in 4x13 list:

list = [[0]*13 for i in range(4)]

x1 = 0
y1 = 0

x2 = 0

counter = 0

while x1 < len(list):
    while y1 < len(list[0]):
        list[x1][y1] = 1
        x2 = x1
        y2 = y1   1
        while x2 < len(list):

            while y2 < len(list[0]):
                list[x2][y2] = 1
                print(list)
                counter  = 1
                if counter00000 == 0:
                    print(counter)
                list[x2][y2] = 0
                y2  = 1
            y2 = 0
            x2  = 1

        list[x1][y1] = 0
        y1  = 1
    y1 = 0
    x1  = 1

print()
print(counter)

but to remake this code for 7 elements (which means using nested loop inside nested loop inside nested loop... - 6 times) seems to me as utter hell... Could there be some other way, please?

CodePudding user response：

Normally you definitely want a run time below O(n^2). n is the number of items, in your case 4*13. The best version of a script will be about twice as much run time. - This is without analyzes whether you can reuse data or other data structure can be an advantage.

But here is a script that has less run time than your example O(n^14).

rows = 4 # The four colors
col = 13 # Number of cards
max_range = 7 # 7 cards

total = rows*col # See the rows and columns as just a list of values
counter = 0

for i in range(total - max_range   1): # Go through all minus the range
    # Create a list of zeros and set the range to 1
    _list = [[0]*col for i in range(rows)]
    for i2 in range(i, i   max_range):
        _list[int(i2/col)][i2%col] = 1
    print(_list)

    # Move each value in the range to the end
    for i2 in range(1, max_range):
        end = total - i2
        for i3 in range(i   max_range - i2   1, end   1):
            _list[int((i3-1)/col)][(i3-1)%col] = 0
            _list[int(i3/col)][i3%col] = 1
            print(_list)
            counter  = 1

print("\n"   str(counter))

It will be a very resource demanding method. I think you need to reduce the problem to a more specific problem if you want a workable method.

For example:

Why calculate all the solutions to make a choice?
Can a better data structure make it easier to know what to do?
Analyzes point by point what you need to achieve outside the code
How should the code be split up to do small tasks so that it is possible to keep track of card status

Maybe this can help: Abstract syntax tree

Another thing to keep in mind is that a list of 133 million 0 and 1 will fill at least 133 Mbyt. It will not be a good idea to save the list as it is a lot to spend on just shift cards.

My advice is to find another way.

CodePudding user response：

Regarding your post in the comments:

>>> f([0,0,1])
[[0,0,1],[0,1,0],[1,0,0]]

There's a builtin for this in the itertools module, permutations, which generates all k-length permutations of a sequence without eliminating duplicates which are in different orders.

So to solve your problem, you need to generate all permutations of your list, which has time complexity O(n!) and then remove the duplicates with O(n) complexity.

from itertools import permutations
x=[0,0,1]
print([*{*permutations(x,len(x))}])
#outputs [(1, 0, 0), (0, 0, 1), (0, 1, 0)]