Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>The easiest way to produce your list is to simply do:</p> <pre><code>def comparisons(seq): return [abs(a-b) for a, b in zip(seq, seq[1:])] </code></pre> <p>As to your comparison, the highest value is always going to be the maximum followed by the minimum, repeated. E.g: for length 4:</p> <pre><code>[3, 0, 3, 0] </code></pre> <p>As this will produce the maximum difference each time. There will be one of these maximum differences (of <code>length-1</code>) for each item in the comparison string (of length <code>length-1</code>). Hence the maximum will be <code>(length-1)**2</code>.</p> <p>However, you seemed to imply that the maximum for length 3 was <code>3</code>, so why is <code>[0, 2, 0]</code> not valid (producing <code>[2, 2]</code> which sums to <code>4</code>)?</p> <p>You mentioned that all of the integers from <code>0</code> to <code>length-1</code> must be included, but then this makes some of your examples (e.g: <code>[0, 1, 0]</code>) invalid. This also conflicts with the idea any elements can be repeated (if a list of length n must contain from 0 to n-1, it cannot have repeats).</p> <p>If this case is true, then your question becomes somewhat similar to the problem of creating a dithering matrix.</p> <p>In the case of ordering the range from 0 to len-1, to produce the maximum difference, the optimal algorithm is to work up from 0, and down from len-1, adding the low values to the highest 'side' of the list, and visa versa:</p> <pre><code>from collections import deque from itertools import permutations from operator import itemgetter def comparisons(seq): return [abs(a-b) for a, b in zip(seq, seq[1:])] def best_order(n): temp = deque([0, n-1]) low = 1 high = n-2 while low &lt; high: left = temp[0] right = temp[-1] if left &lt; right: temp.append(low) temp.appendleft(high) else: temp.append(high) temp.appendleft(low) low += 1 high -= 1 if len(temp) &lt; n: temp.append(low) return list(temp) def brute_force(n): getcomp = itemgetter(2) return max([(list(a), comparisons(a), sum(comparisons(a))) for a in permutations(range(n))], key=getcomp) for i in range(2, 6): print("Algorithmic:", best_order(i), comparisons(best_order(i)), sum(comparisons(best_order(i)))) print("Brute Force:", *brute_force(i)) </code></pre> <p>Which gives us:</p> <pre><code>Algorithmic: [0, 1] [1] 1 Brute Force: [0, 1] [1] 1 Algorithmic: [0, 2, 1] [2, 1] 3 Brute Force: [0, 2, 1] [2, 1] 3 Algorithmic: [2, 0, 3, 1] [2, 3, 2] 7 Brute Force: [1, 3, 0, 2] [2, 3, 2] 7 Algorithmic: [3, 0, 4, 1, 2] [3, 4, 3, 1] 11 Brute Force: [1, 3, 0, 4, 2] [2, 3, 4, 2] 11 </code></pre> <p>Showing that this algorithm matches the brute force approach for producing the best result possible.</p> <p>What follows is a more general solution:</p> <pre><code>from collections import deque def comparisons(seq): return [abs(a-b) for a, b in zip(seq, seq[1:])] def best_order(seq): pool = deque(sorted(seq)) temp = deque([pool.popleft(), pool.pop()]) try: while pool: if temp[0] &lt; temp[-1]: temp.append(pool.popleft()) temp.appendleft(pool.pop()) else: temp.append(pool.pop()) temp.appendleft(pool.popleft()) except IndexError: pass return list(temp) i = [0, 1, 2, 3, 4, 5, 6, 0, 0, 1, 1, 2, 2] print("Algorithmic:", best_order(i), comparisons(best_order(i)), sum(comparisons(best_order(i)))) for n in range(2, 6): i = list(range(n)) print("Algorithmic:", best_order(i), comparisons(best_order(i)), sum(comparisons(best_order(i)))) </code></pre> <p>Which gives:</p> <pre><code>Algorithmic: [2, 1, 3, 0, 5, 0, 6, 0, 4, 1, 2, 1, 2] [1, 2, 3, 5, 5, 6, 6, 4, 3, 1, 1, 1] 38 Algorithmic: [0, 1] [1] 1 Algorithmic: [0, 2, 1] [2, 1] 3 Algorithmic: [2, 0, 3, 1] [2, 3, 2] 7 Algorithmic: [3, 0, 4, 1, 2] [3, 4, 3, 1] 11 </code></pre> <p>Which matches the previous results where it can.</p>
    singulars
    1. This table or related slice is empty.
    1. POComparison between adjacent elements in sequences
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USGareth Latty
    1. USGareth Latty
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POComparison between adjacent elements in sequences
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    1. CO@MarcosdaSilvaSampaio See my update, I think this is what you are looking for.
      singulars
      1. PO
      1. USGareth Latty
    2. COGreat! I only would change `permutations(range(n))`. I need to include some valid sequences, like [0, 1, 0] and [1, 0, 1].
      singulars
      1. PO
      1. USmsampaio
    3. CO@MarcosdaSilvaSampaio Well, that part is only for the brute forcing, for comparison. Also, if there are sequences allowed with repeated numbers, this will not work, and the earlier solution (``(length(seq)-1)**2``) is the best, as you can have ``[length(seq)-1, 0, length(seq)-1, 0, ...]``. What are the actual conditions for repeated characters?
      singulars
      1. PO
      1. USGareth Latty
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload