How to sort a list of lists in Python without having repeated names together

Question

I have the following list with names and ages:

[['John', 8], ['John', 8], ['John', 8], ['Mary', 7], ['Mary', 7], ['Mike', 9], ['Mike', 9]]

How to sort it, with Python, in a random way and without having same name next to each other. For example (sorted):

[['John', 8], ['Mary', 7], ['Mike', 9], ['John', 8], ['Mike', 9], ['Mary', 7], ['John', 8]]

My real case has about 250 names and same name does not repeats more than 50 times, that means that always there is a possible solution.

@PranavHosangadi sorry if sounds a bit confusing. Let's say... sort in a random way and, then, relocate the names that are identical and together (sequential), to another position in the list. — Nanno, Feb 13 '23 at 23:48
"and without having same name next to each other" - what will you do if, for example, every name in the input is the same? — Karl Knechtel, Feb 14 '23 at 00:44
@KarlKnechtel never will happens a situation where all and every name is the same. As clarified in my question, the real dataset has 250 names and one single name never repeats more than 50 times. — Nanno, Feb 14 '23 at 00:50
The author has stated that there is a maximum of 50 names the same out of 250. The only time there is an impossible problem set is if there is one name that has > ~50% of the population (depending on the population size). However, the problem is that the definition of "in a random way" is not clear. The random way could be just for the rhs of the name, value pair. Or it could be for the entire result set must be as random as possible. It is an interesting problem but it needs better definition. — Richard Green, Feb 14 '23 at 00:53
@RichardGreen the shuffle solution, as proposed by some guys, is a possible solution, but have no randomness, that means, the names that show few times in the 250 names dataset, will be concentrated on top of the sorted list. While the shuffle is a possible and for sure a valid solution, it will leads that, at the bottom of the sorted list, will be just the two more frequent names in the list. The "randomness" has as purpose to avoid such situation. — Nanno, Feb 14 '23 at 01:00

Andrej Kesely · Answer 1 · 2023-02-14T01:09:18.320

3

Another solution (to get random results). Crate a temporary dictionary where keys are names and values ale lists of values from original data.

Select one element at random (which has most values) and put it as first element in output list, then select at pop at random from lists which have the most values left.

from random import choice

lst = [
    ["John", 8],
    ["John", 8],
    ["John", 8],
    ["Mary", 7],
    ["Mary", 7],
    ["Mike", 9],
    ["Mike", 9],
]

def get_random_max(d):
    m = max(map(len, d.values()))
    return choice([[k, v] for k, v in d.items() if len(v) == m])

tmp = {}
for name, value in lst:
    tmp.setdefault(name, []).append(value)

k, v = get_random_max(tmp)
out = [[k, v.pop()]]

while any(tmp.values()):
    k, v = get_random_max({k: v for k, v in tmp.items() if k != out[-1][0]})
    out.append([k, v.pop()])

print(out)

Prints (for example):

[['John', 8], ['Mary', 7], ['Mike', 9], ['John', 8], ['Mike', 9], ['John', 8], ['Mary', 7]]

EDIT: Incorporated the suggestions from @KellyBundy. Thanks!

edited Feb 14 '23 at 01:09

answered Feb 14 '23 at 00:22

Andrej Kesely

168,389
15
48
91

@KellyBundy Yep, you're right. I've updated the answer (chosed the element with max values as first). – Andrej Kesely Feb 14 '23 at 00:30
1

Ok I think it can't fail anymore (as long as a valid order is possible). But could be "more random". With 50 Johns and 50 Marys and 1 Mike, poor Mike needs to wait until the end. – Kelly Bundy Feb 14 '23 at 01:08
1

@KellyBundy I've added your suggestions to the code :) Thanks! For the "more random" question, I was thinking one could rotate the `out` list random times as the last step to get the fully random answer. – Andrej Kesely Feb 14 '23 at 01:11

Marcus Vdt · Answer 2 · 2023-02-14T03:03:27.343

Simple example with 296 names and without complicated code. Be aware that this code will run forever if you provide unresolvable list, ie. if you lied when you said the list does not contain lots of repetitions of the same names. For your needs, it should work.

Thank you.

import hashlib
import json
import random
mylist=[['John', 8], ['John', 8], ['John', 8], ['Mary', 7], ['Mary', 7], ['Mike', 9], ['Mike', 9],['John', 8], ['John', 8], ['Lucas', 17], ['Lucas', 17], ['Lucas', 17], ['Beatriz', 14], ['Beatriz', 14], ['Gabriela', 14], ['Gabriela', 14], ['John', 8], ['Mary', 7], ['Mary', 7], ['Mike', 9], ['Mike', 9], ['Beatriz', 14], ['Beatriz', 14], ['Gabriela', 14], ['Gabriela', 14], ['John', 8], ['Mary', 7], ['Mary', 7], ['Mike', 9], ['Mike', 9], ['Mary', 7], ['Mary', 7], ['Mike', 9], ['Mike', 9],['John', 8], ['John', 8], ['Lucas', 17],['Marcus', 8], ['Marcus', 8], ['Marcus', 8], ['Maricotas', 7], ['Maricotas', 7], ['Merlin', 9], ['Merlin', 9],['Marcus', 8], ['Marcus', 8], ['Beto', 17], ['Beto', 17], ['Beto', 17], ['Beatriz', 14], ['Beatriz', 14], ['Gabriela', 14], ['Gabriela', 14], ['Marcus', 8], ['Maricotas', 7], ['Maricotas', 7], ['Merlin', 9], ['Merlin', 9], ['Beatriz', 14], ['Beatriz', 14], ['Gabriela', 14], ['Gabriela', 14], ['Marcus', 8], ['Maricotas', 7], ['Maricotas', 7], ['Merlin', 9], ['Merlin', 9], ['Maricotas', 7], ['Maricotas', 7], ['Merlin', 9], ['Merlin', 9],['Marcus', 8], ['Marcus', 8], ['Beto', 17], ['John', 8], ['John', 8], ['John', 8], ['Mary', 7], ['Mary', 7], ['Mike', 9], ['Mike', 9],['John', 8], ['John', 8], ['Lucas', 17], ['Lucas', 17], ['Lucas', 17], ['Beatriz', 14], ['Beatriz', 14], ['Gabriela', 14], ['Gabriela', 14], ['John', 8], ['Mary', 7], ['Mary', 7], ['Mike', 9], ['Mike', 9], ['Beatriz', 14], ['Beatriz', 14], ['Gabriela', 14], ['Gabriela', 14], ['John', 8], ['Mary', 7], ['Mary', 7], ['Mike', 9], ['Mike', 9], ['Mary', 7], ['Mary', 7], ['Mike', 9], ['Mike', 9],['John', 8], ['John', 8], ['Lucas', 17],['Marcus', 8], ['Marcus', 8], ['Marcus', 8], ['Maricotas', 7], ['Maricotas', 7], ['Merlin', 9], ['Merlin', 9],['Marcus', 8], ['Marcus', 8], ['Beto', 17], ['Beto', 17], ['Beto', 17], ['Beatriz', 14], ['Beatriz', 14], ['Gabriela', 14], ['Gabriela', 14], ['Marcus', 8], ['Maricotas', 7], ['Maricotas', 7], ['Merlin', 9], ['Merlin', 9], ['Beatriz', 14], ['Beatriz', 14], ['Gabriela', 14], ['Gabriela', 14], ['Marcus', 8], ['Maricotas', 7], ['Maricotas', 7], ['Merlin', 9], ['Merlin', 9], ['Maricotas', 7], ['Maricotas', 7], ['Merlin', 9], ['Merlin', 9],['Marcus', 8], ['Marcus', 8], ['Beto', 17], ['John', 8], ['John', 8], ['John', 8], ['Mary', 7], ['Mary', 7], ['Mike', 9], ['Mike', 9],['John', 8], ['John', 8], ['Lucas', 17], ['Lucas', 17], ['Lucas', 17], ['Beatriz', 14], ['Beatriz', 14], ['Gabriela', 14], ['Gabriela', 14], ['John', 8], ['Mary', 7], ['Mary', 7], ['Mike', 9], ['Mike', 9], ['Beatriz', 14], ['Beatriz', 14], ['Gabriela', 14], ['Gabriela', 14], ['John', 8], ['Mary', 7], ['Mary', 7], ['Mike', 9], ['Mike', 9], ['Mary', 7], ['Mary', 7], ['Mike', 9], ['Mike', 9],['John', 8], ['John', 8], ['Lucas', 17],['Marcus', 8], ['Marcus', 8], ['Marcus', 8], ['Maricotas', 7], ['Maricotas', 7], ['Merlin', 9], ['Merlin', 9],['Marcus', 8], ['Marcus', 8], ['Beto', 17], ['Beto', 17], ['Beto', 17], ['Beatriz', 14], ['Beatriz', 14], ['Gabriela', 14], ['Gabriela', 14], ['Marcus', 8], ['Maricotas', 7], ['Maricotas', 7], ['Merlin', 9], ['Merlin', 9], ['Beatriz', 14], ['Beatriz', 14], ['Gabriela', 14], ['Gabriela', 14], ['Marcus', 8], ['Maricotas', 7], ['Maricotas', 7], ['Merlin', 9], ['Merlin', 9], ['Maricotas', 7], ['Maricotas', 7], ['Merlin', 9], ['Merlin', 9],['Marcus', 8], ['Marcus', 8], ['Beto', 17], ['John', 8], ['John', 8], ['John', 8], ['Mary', 7], ['Mary', 7], ['Mike', 9], ['Mike', 9],['John', 8], ['John', 8], ['Lucas', 17], ['Lucas', 17], ['Lucas', 17], ['Beatriz', 14], ['Beatriz', 14], ['Gabriela', 14], ['Gabriela', 14], ['John', 8], ['Mary', 7], ['Mary', 7], ['Mike', 9], ['Mike', 9], ['Beatriz', 14], ['Beatriz', 14], ['Gabriela', 14], ['Gabriela', 14], ['John', 8], ['Mary', 7], ['Mary', 7], ['Mike', 9], ['Mike', 9], ['Mary', 7], ['Mary', 7], ['Mike', 9], ['Mike', 9],['John', 8], ['John', 8], ['Lucas', 17],['Marcus', 8], ['Marcus', 8], ['Marcus', 8], ['Maricotas', 7], ['Maricotas', 7], ['Merlin', 9], ['Merlin', 9],['Marcus', 8], ['Marcus', 8], ['Beto', 17], ['Beto', 17], ['Beto', 17], ['Beatriz', 14], ['Beatriz', 14], ['Gabriela', 14], ['Gabriela', 14], ['Marcus', 8], ['Maricotas', 7], ['Maricotas', 7], ['Merlin', 9], ['Merlin', 9], ['Beatriz', 14], ['Beatriz', 14], ['Gabriela', 14], ['Gabriela', 14], ['Marcus', 8], ['Maricotas', 7], ['Maricotas', 7], ['Merlin', 9], ['Merlin', 9], ['Maricotas', 7], ['Maricotas', 7], ['Merlin', 9], ['Merlin', 9],['Marcus', 8], ['Marcus', 8], ['Beto', 17]]
mylen=len(mylist)
print('Old list has:' + str(mylen))
print(mylist)
data_md5 = hashlib.md5(json.dumps(mylist, sort_keys=True).encode('utf-8')).hexdigest()
print(data_md5)
previtem=['','']
endlist=[]
while mylen > 1:
    myrand=random.randrange(0, mylen-1)
    selected=mylist[myrand]
    if selected!=previtem:
        tmpitem=mylist.pop(myrand)
        mylen=len(mylist)
        endlist.append(selected)
        previtem=selected
print('-----')
print('--Looking where to insert last item--')
for i in range(1,len(endlist)):
    if (endlist[i-1]!=mylist) and (endlist[i]!=mylist):
        break
endlist.insert(i, mylist)
print('New list has:' + str(len(endlist)))
print(endlist)
data_md5 = hashlib.md5(json.dumps(endlist, sort_keys=True).encode('utf-8')).hexdigest()
print(data_md5)

I have added MD5 checksum calc to prove that the second list changes on every run while the first one stays the same. — Marcus Vdt, Feb 14 '23 at 03:04

score 0 · Accepted Answer · answered Feb 22 '23 at 15:39

Thank you for all the answers and suggestions.

Unfortunately I could not adapt any of the proposed solutions to work with my real data, and I had to develop a solution, that you can see and comment here:

Python: sorting a matrix of data (list of lists) to have equal "names" at the biggest distance of each other

How to sort a list of lists in Python without having repeated names together

3 Answers3

Linked