Newbie algorithm design [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question appears to be off-topic because it lacks sufficient information to diagnose the problem. Describe your problem in more detail or include a minimal example in the question itself.

Closed 9 years ago.

Improve this question

I'm new to algorithm design. I have a list of about 8128 integers. I need to create an algorithm that will create 128 different combinations of unique numbers.

The first number, 1, is'nt used by any combination. The first 6 number sequences begin as follows:

1. 2,4,7,11,16,22
2. 3,6,10,15,21
3. 5,9,14,20
4. 8,13,19
5. 12,18
6. 17

I notice that the interval between numbers increases by 1 between each sequence. I also see that it seems to pick the first unique(non-used) integer to begin a sequence. I'm stuck trying to implement this in Python.

I want to solve a facility location problem. I have 8128 distance values stored in an array. The code snippet below gets the first two relative distance arrays correct, but the 3rd repeats a value that has already been used before

distances = [[0 for col in range(2)] for row in range(128)] #this array contains line numbers that contain distances

#1st iteration works
startpoint = 0
count = 1
diff = 2

while startpoint < 8127:
    print distance[startpoint+diff]
    startpoint = startpoint+count
    count += 1
    diff += 2

#2nd iteration works
startpoint = 1
count = 2
diff = 3

while startpoint < 8127:
    print distance[startpoint+diff]
    startpoint = startpoint+count
    count += 1
    diff += 2

#3rd iteration repeats a value
startpoint = 2
count = 3
diff = 4

while startpoint < 8127:
    print distance[startpoint+diff]
    startpoint = startpoint+count
    count += 1
    diff += 2

Is there an example or an implementation of this algorithm out there?

Answer 1

The distance is maybe better represented as a function than as an array:

D(I, J) = I + J

where I and J are the (un-Pythonesuqe) one-based indices. (Do you realise that in your code, the distances are all zero?)

Also, you should probably be thinking in terms of your number of rows (128) rather than in terms of overall number of values (8128). The purpose of your three iterations is not clear to me. Shouldn't you have loops over rows and columns?

Anyway:

N = 128
n = 2

for i in range(N):
    m = n
    s = []
    for j in range(N - i):
        s.append(m)
        m += (j + 1) + (i + 1)

    print i + 1, s        
    n += i + 1

You can solve this in another way by noticing that every number occurs only once and follows a pattern:

 2   4   7  11
    /   /   /
   /   /   /
  /   /   /
 3   6  10
    /   /
   /   /
  /   /
 5   9
    / 
   / 
  / 
 8

Then you can create all lists up front and print them in a second loop:

n = 2
L = []

for i in range(N):
    L.append([])

    for LL in reversed(L):
        LL.append(n)
        n += 1

for i, LL in enumerate(L):
    print i + 1, LL