How to go through a double for loop randomly in python

Question

Consider the following code:

for i in range(size-1):
    for j in range(i+1,size):
        print((i,j))

I need to go through this for-loop in a random fashion. I attempt to write a generator to do such a thing

def Neighborhood(size):
    for i in shuffle(range(size-1)):
        for j in shuffle(range(i+1), size):
            yield i, j
for i,j in Neighborhood(size):
    print((i,j))

However, shuffle cannot be applied to whatever object range is. I do not know how to remedy the situation, and any help is much appreciated. I would prefer a solution avoid converting range to a list, since I need speed. For example, size could be on the order of 30,000 and i will do perform this for loop around 30,000 times.

I also plan to escape the for loop early, so I want to avoid solutions that incorporate shuffle(list(range(size)))

You can use `list(range())` if you actually need to shuffle it — OneCricketeer, Sep 21 '17 at 02:45
I think what you're asking for is impossible. You want to go through every possible combination of (i, j) in a random order, but if you don't want repeats it's necessary to remember which combinations you've already used. That requires O(size^2) space. But I think you *can* do slightly better than shuffle(range). — Jeremy McGibbon, Sep 21 '17 at 02:46
It's implied by "I need to go through this for-loop in a random fashion". But perhaps Johnathan will clarify. — Jeremy McGibbon, Sep 21 '17 at 02:49
Is it OK that, even with shuffling, you're going over your triangle one row at a time? — Davis Herring, Sep 21 '17 at 02:55
I'm coding up a local search algorithm. The for loop generates neighbors of a configuration and I escape the for loop when I find an improved configuration so I will not go through the entire for loop a lot of the time — Jonathan Davidson, Sep 21 '17 at 02:57
You certainly can avoid going row-by-row since it's easy to derive `(i,j)` from a flat index. Then you can use the [encryption technique](https://stackoverflow.com/questions/28990820/iterator-to-produce-unique-random-order) on the indices. — Davis Herring, Sep 21 '17 at 03:17

Kaushik NP · Accepted Answer · 2017-09-21T03:33:33.220

2

You can use random.sample.

The advantage of using random.sample over random.shuffle, is , it can work on iterators, so in :

Python 3.X you don't need to convert range() to list
In Python 2,X, you can use xrange
Same Code can work in Python 2.X and 3.X

Sample code :

n=10
l1=range(n)
for i in sample(l1,len(l1)):
    l2=range(i,n)
    for j in sample(l2,len(l2)):
        print(i,j)

Edit :

As to why I put in this edit, go through the comments.

def Neighborhood(size):
    range1 = range(size-1)
    for i in sample(range1, len(range1)):
        range2 = range(i+1)
        for j in sample(range2, len(range2)):
            yield i, j

edited Sep 21 '17 at 03:33

answered Sep 21 '17 at 03:01

Kaushik NP

6,733
9
31
60

I have given everything that the OP needs. Its not our job to spoon feed others. As they say, its better to teach others to fish than to hand the fish over to them. – Kaushik NP Sep 21 '17 at 03:12
1

Thanks for your input @KaushikNP – Jonathan Davidson Sep 21 '17 at 03:19
Sure. Glad to help @JonathanDavidson . And don't think I don't know who down voted on my answer here Stefan Pochmann – Kaushik NP Sep 21 '17 at 03:21
@JonathanDavidson let me know if you need any help in implementation :) – Kaushik NP Sep 21 '17 at 03:21
The implementation for your response should be straightforward, but thanks for the offer. – Jonathan Davidson Sep 21 '17 at 03:33
Have edited the answer with implementation too. Kudos – Kaushik NP Sep 21 '17 at 03:34

Stefan Pochmann · Answer 2 · 2017-09-21T03:44:48.797

1

A simple way to go really random, not row-by-row:

def Neighborhood(size):
    yielded = set()
    while True:
        i = random.randrange(size)
        j = random.randrange(size)
        if i < j and (i, j) not in yielded:
            yield i, j
            yielded.add((i, j))

Demo:

for i, j in Neighborhood(30000):
    print(i, j)

Prints something like:

2045 5990
224 5588
1577 16076
11498 15640
15219 28006
8066 10142
7856 8248
17830 26616
...

Note: I assume you're indeed going to "escape the for loop early". Then this won't have problems with slowing down due to pairs being produced repeatedly.

edited Sep 21 '17 at 03:44

answered Sep 21 '17 at 03:30

Stefan Pochmann

27,593
8
44
107

This is definitely an approach I will try to implement along with the other suggestions in the thread, especially in tandem with simulated annealing. Can I modify the code so that it runs as a generator, that way I don't create the entire set ahead of time, or does this code already due this. Sorry I'm new to generators and the yield command. – Jonathan Davidson Sep 21 '17 at 04:23
@JonathanDavidson It already is a generator. Btw, you said you "want to avoid solutions that incorporate shuffle(list(range(size)))" but then you accepted one that practically does exactly that... – Stefan Pochmann Sep 21 '17 at 14:16
I thought sampling an iterator does not do that. My mistake. I have already tried both yours and the other solution, in different versions of my algorithm and I am testing to see which approach works better. I appreciate your contribution. – Jonathan Davidson Sep 21 '17 at 19:51

OneCricketeer · Answer 3 · 2017-09-21T13:22:59.437

-1

I don't think you can randomly traverse an Iterator. You can predefine the shuffled lists, though

random iteration in Python

L1 = list(range(size-1))
random.shuffle(L1) 
for i in L1:
    L2 = list(range(i+1, size))
    random.shuffle(L2) 
    for j in L2:
        print((i,j))

Of course, not optimal for large lists

edited Sep 21 '17 at 13:22

answered Sep 21 '17 at 02:50

OneCricketeer

179,855
19
132
245

How to go through a double for loop randomly in python

3 Answers3