Szukam algorytmu do dystrybucji wartości z listy, aby powstała lista była jak najbardziej „zrównoważona” lub „równomiernie rozłożona” (w cudzysłowie, ponieważ nie jestem pewien, czy są to najlepsze sposoby na opisanie jej ... później przedstawię sposób pomiaru, czy wynik jest lepszy niż inny).

Tak więc dla listy:

[1, 1, 2, 2, 3, 3]

Jednym z najlepszych rezultatów po ponownej dystrybucji wartości jest:

[1, 2, 3, 1, 2, 3]

Mogą występować inne wyniki tak dobre jak ten i oczywiście komplikuje się to z mniej jednolitym zestawem wartości.

Oto jak zmierzyć, czy wynik jest lepszy niż inny:

1. Policz odległości między każdym przedmiotem a następnym przedmiotem o tej samej wartości.

2. Oblicz odchylenie standardowe dla tego zestawu odległości. Niższa dyspersja oznacza lepszy wynik.

Obserwacje:

• Przy obliczaniu odległości i osiągnięciu końca listy bez znalezienia elementu o tej samej wartości wracamy do początku listy. Co najwyżej ten sam element zostanie znaleziony, a odległość dla tego elementu będzie długością listy. Oznacza to, że lista jest cykliczna ;
• Typowa lista zawiera ~ 50 pozycji o ~ 15 różnych wartościach w różnych ilościach.

Więc:

• W rezultacie [1, 2, 3, 1, 2, 3]odległości są [3, 3, 3, 3, 3, 3], a odchylenie standardowe wynosi 0;
• W rezultacie [1, 1, 2, 2, 3, 3]odległości są [1, 5, 1, 5, 1, 5], a odchylenie standardowe wynosi 2;
• Co sprawia, że ​​pierwszy wynik jest lepszy od drugiego (niższe odchylenie jest lepsze).

Biorąc pod uwagę te definicje, proszę o wskazówkę, których algorytmów lub strategii powinienem szukać.

Natknąłem się na to pytanie, badając podobny problem: optymalne dodatki płynów w celu zmniejszenia stratyfikacji. Wygląda na to, że moje rozwiązanie dotyczyłoby również twojej sytuacji.

Jeśli chcesz mieszać ciecze A, B i C w proporcji 30, 20, 10 (to znaczy 30 jednostek A, 20 jednostek B i 10 jednostek C), otrzymujesz rozwarstwienie, jeśli dodasz wszystkie A, potem wszystkie B, a potem wszystkie C. Lepiej mieszaj mniejsze jednostki. Na przykład wykonaj dodawanie pojedynczych jednostek w sekwencji [A, B, A, C, B, A]. To całkowicie zapobiegnie rozwarstwieniu.

Znalazłem sposób, aby to potraktować jako rodzaj scalenia, używając kolejki priorytetowej. Jeśli utworzę strukturę do opisania dodatków:

MergeItem
    Item, Count, Frequency, Priority

Częstotliwość jest wyrażana jako „jeden na N”. Zatem A, który jest dodawany trzy z sześciu razy, ma częstotliwość 2 (6/3).

I zainicjuj stertę, która początkowo zawiera:

(A, 3, 2, 2)
(B, 2, 3, 3)
(C, 1, 6, 6)

Teraz usuwam pierwszy element ze sterty i wysyłam go. Następnie zmniejsz jego liczbę o 1 i zwiększ Priorytet o Częstotliwość i dodaj go z powrotem do stosu. Wynikowa sterta to:

(B, 2, 3, 0)
(A, 2, 2, 4)
(C, 1, 6, 6)

Następnie usuń B ze sterty, wydrukuj i zaktualizuj, a następnie dodaj z powrotem do sterty:

(A, 2, 2, 4)
(C, 1, 6, 6)
(B, 1, 3, 6)

Jeśli będę kontynuować w ten sposób, otrzymam pożądaną mieszankę. Korzystam z niestandardowego modułu porównującego, aby upewnić się, że gdy do stosu zostaną wstawione elementy o równym priorytecie, najpierw zostanie zamówiony ten o najwyższej wartości częstotliwości (tj. Najmniejszej częstotliwości).

Na blogu napisałem pełniejszy opis problemu i jego rozwiązania oraz przedstawiłem działający kod C #, który to ilustruje. Zobacz Równomierne rozmieszczenie elementów na liście .

Zaktualizuj po komentarzach

Myślę, że mój problem jest podobny do problemu PO i dlatego moje rozwiązanie jest potencjalnie przydatne. Przepraszam, że nie sformułowałem mojej odpowiedzi bardziej w kontekście pytania PO.

Pierwszy zarzut, że moje rozwiązanie używa A, B i C zamiast 0, 1 i 2, można łatwo naprawić. To po prostu kwestia nomenklatury. Uważam, że łatwiej i mniej myląco jest myśleć i mówić „dwa A” niż „dwa 1”. Ale na potrzeby tej dyskusji zmodyfikowałem swoje wyniki poniżej, aby użyć nomenklatury PO.

Oczywiście mój problem dotyczy pojęcia odległości. Jeśli chcesz „rozłożyć równomiernie”, sugeruje się odległość. Ale znowu to moja wina, że ​​nie pokazałem odpowiednio, jak mój problem jest podobny do problemu PO.

Przeprowadziłem kilka testów z dwoma przykładami dostarczonymi przez PO. To jest:

[1,1,2,2,3,3]  // which I converted to [0,0,1,1,2,2]
[0,0,0,0,1,1,1,2,2,3]

W mojej nomenklaturze są one wyrażone odpowiednio jako [2,2,2] i [4,3,2,1]. Oznacza to, że w ostatnim przykładzie „4 elementy typu 0, 3 elementy typu 1, 2 elementy typu 2 i 1 element typu 3.”

Uruchomiłem program testowy (jak opisano bezpośrednio poniżej) i opublikowałem swoje wyniki. Brak wkładu OP, nie mogę powiedzieć, czy moje wyniki są podobne, gorsze lub lepsze od jego. Nie mogę też porównywać moich wyników z wynikami innych osób, ponieważ nikt inny ich nie opublikował.

Mogę jednak powiedzieć, że algorytm stanowi dobre rozwiązanie mojego problemu eliminacji stratyfikacji podczas mieszania cieczy. I wygląda na to, że zapewnia rozsądne rozwiązanie problemu PO.

Do pokazanych poniżej wyników użyłem algorytmu, który opisałem szczegółowo w moim wpisie na blogu, z początkowym priorytetem ustawionym na Frequency/2, a moduł porównujący sterty został zmodyfikowany, aby faworyzować częstszy element. Zmodyfikowany kod jest pokazany tutaj, z komentarzem zmodyfikowanych linii.

private class HeapItem : IComparable<HeapItem>
{
    public int ItemIndex { get; private set; }
    public int Count { get; set; }
    public double Frequency { get; private set; }
    public double Priority { get; set; }

    public HeapItem(int itemIndex, int count, int totalItems)
    {
        ItemIndex = itemIndex;
        Count = count;
        Frequency = (double)totalItems / Count;
        // ** Modified the initial priority setting.
        Priority = Frequency/2;
    }

    public int CompareTo(HeapItem other)
    {
        if (other == null) return 1;
        var rslt = Priority.CompareTo(other.Priority);
        if (rslt == 0)
        {
            // ** Modified to favor the more frequent item.
            rslt = Frequency.CompareTo(other.Frequency);
        }
        return rslt;
    }
}

Uruchamiając mój program testowy z pierwszym przykładem OP, otrzymuję:

Counts: 2,2,2
Sequence: 1,0,2,1,0,2
Distances for item type 0: 3,3
Stddev = 0
Distances for item type 1: 3,3
Stddev = 0
Distances for item type 2: 3,3
Stddev = 0

Mój algorytm działa więc na trywialny problem polegający na tym, że wszystkie liczby są równe.

W przypadku drugiego problemu opublikowanego przez PO otrzymałem:

Counts: 4,3,2,1
Sequence: 0,1,2,0,1,3,0,2,1,0
Distances for item type 0: 3,3,3,1
Stddev = 0.866025403784439
Distances for item type 1: 3,4,3
Stddev = 0.471404520791032
Distances for item type 2: 5,5
Stddev = 0
Distances for item type 3: 10
Stddev = 0
Standard dev: 0.866025403784439,0.471404520791032,0,0

Nie widzę oczywistego sposobu na poprawę tego. Można to zmienić, aby uzyskać odległości dla pozycji 0 [2,3,2,3] lub innego ustawienia 2 i 3, ale to zmieni odchylenia dla pozycji 1 i / lub 2. Naprawdę nie wiem co „optymalne” jest w tej sytuacji. Czy lepiej jest mieć większe odchylenie w przypadku częstszych lub rzadszych przedmiotów?

Nie mając innych problemów z OP, wykorzystałem jego opisy, by stworzyć kilka własnych. W swoim poście powiedział:

Typowa lista zawiera ~ 50 pozycji o ~ 15 różnych wartościach w różnych ilościach.

Więc moje dwa testy to:

[8,7,6,5,5,4,3,3,2,2,2,1,1,1,1]  // 51 items, 15 types
[12,6,5,4,4,3,3,3,2,2,2,1,1]     // 48 items, 13 types

A moje wyniki:

Counts: 8,7,6,5,5,4,3,3,2,2,2,1,1,1,1
Sequence: 0,1,2,3,4,5,7,6,0,1,2,8,9,10,4,3,0,1,5,2,0,1,3,4,6,7,14,11,13,12,0,2,5,1,0,3,4,2,8,10,9,1,0,7,6,5,3,4,2,1,0
Distances for item type 0: 8,8,4,10,4,8,8,1
Stddev = 2.82566363886433
Distances for item type 1: 8,8,4,12,8,8,3
Stddev = 2.76272565797339
Distances for item type 2: 8,9,12,6,11,5
Stddev = 2.5
Distances for item type 3: 12,7,13,11,8
Stddev = 2.31516738055804
Distances for item type 4: 10,9,13,11,8
Stddev = 1.72046505340853
Distances for item type 5: 13,14,13,11
Stddev = 1.08972473588517
Distances for item type 6: 17,20,14
Stddev = 2.44948974278318
Distances for item type 7: 19,18,14
Stddev = 2.16024689946929
Distances for item type 8: 27,24
Stddev = 1.5
Distances for item type 9: 28,23
Stddev = 2.5
Distances for item type 10: 26,25
Stddev = 0.5
Distances for item type 11: 51
Stddev = 0
Distances for item type 12: 51
Stddev = 0
Distances for item type 13: 51
Stddev = 0
Distances for item type 14: 51
Stddev = 0

I dla drugiego przykładu:

Counts: 12,6,5,4,4,3,3,3,2,2,2,1,1
Sequence: 0,1,2,0,3,4,7,5,6,0,1,8,9,10,0,2,0,3,4,1,0,2,6,7,5,12,11,0,1,0,3,4,2,0,1,10,8,9,0,7,5,6,0,
4,3,2,1,0
Distances for item type 0: 3,6,5,2,4,7,2,4,5,4,5,1
Stddev = 1.68325082306035
Distances for item type 1: 9,9,9,6,12,3
Stddev = 2.82842712474619
Distances for item type 2: 13,6,11,13,5
Stddev = 3.44093010681705
Distances for item type 3: 13,13,14,8
Stddev = 2.34520787991171
Distances for item type 4: 13,13,12,10
Stddev = 1.22474487139159
Distances for item type 5: 17,16,15
Stddev = 0.816496580927726
Distances for item type 6: 14,19,15
Stddev = 2.16024689946929
Distances for item type 7: 17,16,15
Stddev = 0.816496580927726
Distances for item type 8: 25,23
Stddev = 1
Distances for item type 9: 25,23
Stddev = 1
Distances for item type 10: 22,26
Stddev = 2
Distances for item type 11: 48
Stddev = 0
Distances for item type 12: 48
Stddev = 0

To „pachnie”, jakby mogło być trudne do NP. Co robisz, gdy masz problem z NP? Rzuć na nią heurystykę, algorytm aproksymacyjny lub użyj solvera SAT.

W twoim przypadku, jeśli nie potrzebujesz absolutnie optymalnego rozwiązania, jednym rozsądnym punktem wyjścia może być próba symulowanego wyżarzania . Istnieje naturalny sposób, aby wziąć dowolne rozwiązanie kandydata i przenieść je do pobliskiego rozwiązania kandydata: losowo wybierz dwa elementy z listy i zamień je. Symulowane wyżarzanie będzie iteracyjnie próbowało ulepszyć rozwiązanie. Możesz znaleźć wiele zasobów na temat symulowanego wyżarzania, jeśli nie znasz go. Możesz także eksperymentować z innymi zestawami „lokalnych ruchów”, które wprowadzają niewielkie zmiany do rozwiązania kandydującego, z nadzieją na stopniowe jego ulepszanie (tj. Zmniejszanie standardowego odchylenia odległości).

$t$$\le t$$\le t^2$$x_{i,j}$$x_{i,j}$$i$$j$$\le t^2$

Ale proponuję zacząć od symulowanego wyżarzania. To pierwsza rzecz, której spróbuję, ponieważ myślę, że to może po prostu zadziałać.

Szkic algorytmu heurystycznego

Nie mam dokładnego rozwiązania tego problemu. Ale ponieważ komentarz Raphaela sugeruje, że wygląda to na problem z podziałem, dla którego opracowano algorytmy heurystyczne, spróbuję zastosować podejście heurystyczne. To tylko szkic algorytmu heurystycznego.

$v$$n$$[1..n]$$i$$n_i$

$n$$vn$$vn/n$$v$

$v$

$i$$n/n_i$$n\mod n_i$$n/n_i$

To poprowadzi nasz algorytm.

$n$

$i$$|n/n_i -v|$

Na początku może to być wartość z bardzo małą liczbą wystąpień. Myślę, że tak naprawdę to nie robi różnicy, ponieważ ograniczenia tworzone przez zajmowanie miejsc są proporcjonalne do liczby dobrze umiejscowionych wartości (?).

Pierwszą rozważaną wartość można umieścić bez żadnych ograniczeń. Następnie pozostałe wartości należy umieścić w taki sposób, aby zminimalizować ich udział w odchyleniu standardowym, ale tylko w miejscach wolnych od dowolnych wcześniej wprowadzonych wartości.

Umieszczenie wystąpień wartości w pozostałych gniazdach można wykonać za pomocą algorytmu programowania dynamicznego, aby scalić obliczenia, które umieszczają tę samą liczbę wartości między dwiema pozycjami, zachowując tylko te, które mają minimalny udział w odchyleniu standardowym (tj. minimalna wartość sumy kwadratu ich odchyleń).

$v$

$j$$|n/n_j -v|$

Następnie umieszczasz wartości singletonów w pozostałych gniazdach.

Uważam, że powinno to ogólnie dać rozsądne rozwiązanie, ale nie mam jeszcze pojęcia, jak to udowodnić lub oszacować lukę za pomocą optymalnego rozwiązania.

Wygląda na to, że jestem bardzo spóźniony na imprezę, ale wysyłam pocztę na wypadek, gdyby ktoś znów się na to natknął. Moje rozwiązanie jest podobne do plus @ babou. Wcześniej miałem problem z harmonogramem w systemie osadzonym, który zaprowadził mnie do tego wątku. Mam implementację specyficzną dla mojego problemu w C, ale pomyślałem, że opublikuję tutaj bardziej ogólne rozwiązanie w Pythonie (wersja C jest skomplikowana przez to, że ograniczyłem się do małego, stałego rozmiaru stosu i bez pamięci alokacje, więc wykonuję cały algorytm na miejscu). Technika wygładzania zastosowana poniżej to coś, czego możesz użyć do narysowania linii na ekranie w 2-bitowym kolorze. Algorytm tutaj osiąga niższy wynik (tj. Lepszy), mierzony za pomocą sumy standardowego odchylenia dla danych wejściowych używanych przez Jima Mischela niż to konkretne rozwiązanie.

def generate(item_counts):
'''item_counts is a list of counts of "types" of items. E.g., [3, 1, 0, 2] represents
   a list containing [1, 1, 1, 2, 4, 4] (3 types of items/distinct values). Generate
   a new list with evenly spaced values.'''
# Sort number of occurrences by decreasing value.
item_counts.sort(reverse=True)
# Count the total elements in the final list.
unplaced = sum(item_counts)
# Create the final list.
placements = [None] * unplaced

# For each type of item, place it into the list item_count times.
for item_type, item_count in enumerate(item_counts):
    # The number of times the item has already been placed
    instance = 0
    # Evenly divide the item amongst the remaining unused spaces, starting with
    # the first unused space encountered.
    # blank_count is the number of unused spaces seen so far and is reset for each
    # item type.
    blank_count = -1
    for position in range(len(placements)):
        if placements[position] is None:
            blank_count += 1
            # Use an anti-aliasing technique to prevent bunching of values.
            if blank_count * item_count // unplaced == instance:
                placements[position] = item_type
                instance += 1
    # Update the count of number of unplaced items.
    unplaced -= item_count

return placements

wyniki dla

Input counts: 8,7,6,5,5,4,3,3,2,2,2,1,1,1,1
Sum of stddev: 16.8 (vs. 22.3 via Jim Mischel)

Input of counts: 12,6,5,4,4,3,3,3,2,2,2,1,1
Sum of stddev: 18.0 (vs. 19.3 via Jim Mischel)

Jeśli dane wejściowe formularza określone przez @moraes, można przekonwertować go do formularza używanego przez tę funkcję w krokach O (n) przy użyciu bitów pamięci Big Omega (n * log (n)), gdzie n jest liczbą elementów ( na liście zawierającej 255 elementów nie będziesz potrzebował więcej niż 255 dodatkowych bajtów), utrzymując równoległą tablicę z liczbą powtórzeń. Alternatywnie można wykonać parę sortowań na miejscu z dodatkową pamięcią O (1).

PS

import numpy
import collections

def evaluate(l):
    '''Given a distribution solution, print the sum of stddevs for each type in the solution.'''
    l2 = l * 2
    distances = [None] * len(l)
    distance_dict = collections.defaultdict(list)
    for i in range(len(l)):
        distances[i] = l2.index(l[i], i + 1) - i
        distance_dict[l[i]].append(l2.index(l[i], i + 1) - i)

    keys = list(distance_dict.keys())
    keys.sort()
    score = 0
    # Calculate standard deviations for individual types.
    for key in keys:
        sc = numpy.std(distance_dict[key])
        score += sc
    print('Stddev sum: ', score)

Edycja: Wiem, że to rozwiązanie nie zapewnia optymalnej wydajności przez kontrprzykład. Wkład [6, 2, 1]produkcji [0, 1, 0, 0, 2, 0, 0, 1, 0]; lepszym rozwiązaniem jest [0, 0, 1, 0, 2, 0, 0, 1, 0].

Ten algorytm działa z tablicą liczb całkowitych, gdzie każda liczba całkowita reprezentuje inną kategorię. Tworzy osobne tablice dla każdej kategorii. Na przykład, jeśli tablica początkowa to [1, 1, 1, 2, 2, 3], utworzy trzy tablice, [3], [2, 2], [1, 1, 1].

Stamtąd rekurencyjnie łączy dwie najmniejsze tablice (w tym przykładzie [3] i [2,2]) i rozmieszcza rozmieszczenie elementów mniejszej tablicy w drugiej najmniejszej tablicy w oparciu głównie o stosunek liczby wystąpień większych i mniejszych kategorii. W tym przykładzie zakończymy z [2,3,2]. Następnie użyłby tej tablicy jako mniejszej tablicy, która zostanie połączona w następną większą tablicę, dopóki nie zostanie tylko jedna tablica.

<?php
/**
 *This will separete the source array into separate arrays for each category
 */
function splitArrayByCategory($source) {

    //  index is the category, value is the tally
    $categoryCounts  = array_count_values($source);

    // Sort that list, keep index associations
    asort($categoryCounts);

    // build separate arrays for each category
    // index = order, smaller index = smaller category count
    // value = array of each category
    $separated = array();
    foreach ($categoryCounts as $category => $tally)
        $separated[] = array_fill(0, $tally, $category);

    return $separated;
}

/**
 * Will take the array of arrays generated by splitArrayByCategory, and merge
 * them together so categories are evenly distributed
 */
function mergeCategoryArrays($categoryArray) {

    // How many entries are there, for the smallest & second smallest categories
    $smallerCount = count($categoryArray[0]);
    $largerCount  = count($categoryArray[1]);

    // Used to determine how much space there should be between these two categories
    $space = $largerCount/$smallerCount;

    // Merge the array of the smallest category into the array of the second smallest
    foreach ($categoryArray[0] as $domIndex => $domain) {
        // Where should we splice the value into the second array?
        $location = floor($domIndex*$space+$domIndex+($space/2));
        // actually perform the splice
        array_splice($categoryArray[1], $location, 0, $domain);
    }

    // remove the smallest domain we just spliced into the second smallest
    unset($categoryArray[0]);

    // reset the indexes
    $categoryArray = array_values($categoryArray);

    // If we have more than one index left in the categoryArray (i.e. some things
    // still need to get merged), let's re-run this function,
    if (count($categoryArray)>1)
        $categoryArray = mergeCategoryArrays($categoryArray);

    return $categoryArray;
}

// The sample list we're working with.
// each integer represents a different category
$listSample = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,5,5,5,5,6,6,7,7,7,7];

// Split the sample list into separate arrays for each category
$listSplitByCategory = splitArrayByCategory($listSample);

// If there are not at least two categories, what's the point?
if (count($listSplitByCategory) < 2) throw new Exception("You need at least two categories");

// perform the actual distribution of categories.
$listEvenlyDistributed = mergeCategoryArrays($listSplitByCategory)[0];

// Display the array before and after the categories are evenly distributed
for ($i=0; $i<count($listSample); $i++) {
    print $listSample[$i].",";
    print $listEvenlyDistributed[$i]."\n";
}

KOD ANSI C

Ten kod działa, wyobrażając sobie linię prostą w n przestrzeni wymiarowej (gdzie n jest liczbą kategorii) przechodzącą przez początek z wektorem kierunkowym (v1, v2, ..., vi, ... vn), gdzie vi jest liczbą pozycje w kategorii i. Zaczynając od początku, celem jest znalezienie następnego najbliższego punktu do linii. Na przykładzie [0 0 0 0 0 1 1 1 2 2 2 3] daje wynik [0 1 2 0 3 1 0 2 0 1 2 0]. Korzystając z przykładu Lungja [0 0 0 0 0 0 1 1 2] otrzymujemy [0 1 0 0 2 0 0 1 0], co jest dokładnie takie samo jak wynik Lungja.

Algorytm jest bardziej wydajny dzięki zastosowaniu tylko arytmetyki liczb całkowitych i uwzględnianiu tylko delt między odległościami od każdego punktu do linii.

# zdefiniować MAXCATEGORIES 100

int main () {int i = 0; int j = 0; int catsize = 0; wektor wewnętrzny [MAXCATEGORIES]; punkt początkowy [MAXCATEGORIES]; int kategorii = 0; int totalitems = 0; int best = 0; długie d2 = 0 l; długie vp = 0L; długie v2 = 0 l; długa delta = 0L; długa beta = 0L;

printf("Enter the size of each category (enter 0 to finish):\r\n");
do
{
    catsize = 0;
    #ifdef _MSVC_LANG
            scanf_s("%d", &catsize);
    #else
            scanf("%d", &catsize)
    #endif
    if (catsize > 0)
    {
        vector[categories] = catsize;
        totalitems += catsize;
        categories++;
    }
} while (catsize > 0);

for (i = 0; i < categories; i++)
{
    v2 += vector[i] * vector[i];
    point[i] = 0;
}

for (i = 0; i < totalitems; i++)
{
    for (j = 0; j < categories; j++)
    {
        delta = (2 * point[j] + 1)*v2 - (2 * vp + vector[j])*vector[j];
        if (j == 0 || delta < beta)
        {
            best = j;
            beta = delta;
        }
    }
    point[best]++;
    vp += vector[best];
    printf("%c ", best + '0');  // Change '0' to 'A' if you like letters instead
}
return 0;

}

moje rozwiązanie:

    vc = train['classes'].value_counts()
    vc = dict(sorted(vc.items()))
    df = pd.DataFrame()
    train['col_for_sort'] = 0.0

    i=1
    for k,v in vc.items():
        step = train.shape[0]/v
        indent = train.shape[0]/(v+1)
        df2 = train[train['classes'] == k].reset_index(drop=True)
        for j in range(0, v):
        df2.at[j, 'col_for_sort'] = indent + j*step + 0.0001*i   
    df= pd.concat([df2,df])
    i+=1

    train = df.sort_values('col_for_sort', ascending=False).reset_index(drop=True)
    del train['col_for_sort']