odtwarzanie zbioru na podstawie innego zbioru

0

mając zbiór np Mapa = (3, 4, 2, 6, 3) tworzony jest zbiór A, w którego skład wchodzą wszystkie elementy mapy oraz sumy sąsiadujących dwójek (3+4,4+2,...), trójek, czwórek itp aż do sumy wszystkich elementów mapy - dla tej konkretnej mapy wyszedłby zbiór A = {2, 3, 3, 4, 6, 6, 7, 8, 9, 9, 11, 12, 15, 15, 18}. Moim zadaniem jest odtworzyć prawidłową kolejność elementów w mapie mając do dyspozycji zbiór A i informację że pierwszy element mapy to zawsze element ostatni A minus element przedostatni A (w tym wypadku 18-15 = 3)

Utknęłam na etapie w którym prawidłowo sprawdzane są tylko pary i nie mogę wpaść na pomysł jak mam sprawdzać trójki, czwórki, bez tworzenia osobnych funkcji. Problemem jest też to że w przypadku tego zbioru A utworzy mi w pierwszej iteracji mapę (3,3,...) ponieważ jest 6 w zbiorze A - ale mapa z 3 na drugim miejscu nie ma prawa istnieć - nie wiem więc jak sprawdzać z góry czy liczba może zająć dane miejsce w mapie jeśli dotychczasowe sumy się zgadzają, ale te z kolejnych iteracji już nie.

int mapowanie( int k, bool * uzyto, int ind, int * jest )
{
    int suma, suma_trojki;
    int warto = false; // do sprawdzania czy warto kontunuowac roziwazanie
    
    if( mapa.size() == k + 1 ) //  jesli na mapie jest juz k+1 elementow (czyli wymagana licznosc)
    {
        cout << "jest";
        * jest == 1;
        return 1;
    }
    else for( int i = 0; i < A.size(); i++ )
    {
        suma = mapa.back();
        
        if( uzyto[ i ] == false )
        {
            suma += A[ i ];
            
            if( suma > A.back() )
            {
                warto = false;
                break;
            }
            else
            for( int j = 0; j < A.size(); j++ )
            {
                if( A[ j ] == suma && uzyto[ j ] == false ) // jesli taka suma jest w zbiorze A i nie jest sumą jakis innych liczb
                {
                    
                    uzyto[ j ] = true;
                    uzyto[ i ] = true;
                    mapa.push_back( A[ i ] );
                    warto = true;
                    break;
                }
            }
        }
        
        if( mapa.size() == k + 1 )
        {
            * jest = 1;
            break;
            return 1;
        }
        if( warto == true ) // jesli rozwiazanie warto kontynuowac bo sumy wystapily w A
             mapowanie( k, uzyto, ind + 1, jest );
        
    }
}

void nieuzyte( int licznosc, bool * odwiedzone )
{
    for( int i = 0; i < licznosc; i++ )
    {
        odwiedzone[ i ] = false;
    }
}
int main()
{
    
    // .....
    
    mapowanie( k, uzyte, 0, & jest );
    
    if( jest == 0 )
         cout << endl << "nie ma rozwiazania" << endl;
    
    
    return 0;
}
0

Trzeba się za to zabrać inaczej, najpierw odtworzyć ile jest elementów w danym zbiorze Mapa, znajac ilośc elementów zbioru A. Widać, że jeśli ta ilość to #A, to:
#A = n + (n - 1) + (n - 2) + ... + (n - (n - 1))
Gdzie n to #Mapa, n - elementy mapy + ilość par (n - 1), trójek, aż do (n - (n - 1)) - suma całego zbioru. Widać, że jest to ilość kolejnych liczb od jeden, które trzeba zsumować, żeby uzyskać #A, a na to jest wzór:
#A = n * (n + 1) / 2
Dla Twojego przykładu 5:
15 = n (n + 1) / 2, rozwiązaniem jest 5.
Mając n wiemy, że n pierwszych elementów A to elementy zbioru Mapa, nie znamy kolejności i wiemy, który jest pierwszy. Teraz nie rozumiem po co to jest posortowane, gdyby nie było to łatwo możnaby przeiterować od elementów n + 1 sprawdzając sumy dwójek, ewentualnie trójek itd...

0

Co do liczności masz racje, mój program ją wylicza wcześniej, ale nie zamieściłam tego fragmentu kodu ( jest to k+1 ). Natomiast co do tego że pierwsze n liczb ze zbioru utworzy mapę - prosty przykład ilustrujący że nie może tak być:
mapa = {2,15,4,2}
daje nam A = {2,2,4,15,17,19,6,21,21,23} co po posortowaniu A = {2,2,4,6,15,17,19,21,21,23} dawałoby jako elementy mapy 2,2,4 oraz 6 - czyli błędnie. Natomiast zbiór A jest na wejściu posortowany by było trudniej rozwiązać to zadanie

lion137 napisał(a):

Trzeba się za to zabrać inaczej, najpierw odtworzyć ile jest elementów w danym zbiorze Mapa, znajac ilośc elementów zbioru A. Widać, że jeśli ta ilość to #A, to:
#A = n + (n - 1) + (n - 2) + ... + (n - (n - 1))
Gdzie n to #Mapa, n - elementy mapy + ilość par (n - 1), trójek, aż do (n - (n - 1)) - suma całego zbioru. Widać, że jest to ilość kolejnych liczb od jeden, które trzeba zsumować, żeby uzyskać #A, a na to jest wzór:
#A = n * (n + 1) / 2
Dla Twojego przykładu 5:
15 = n (n + 1) / 2, rozwiązaniem jest 5.
Mając n wiemy, że n pierwszych elementów A to elementy zbioru Mapa, nie znamy kolejności i wiemy, który jest pierwszy. Teraz nie rozumiem po co to jest posortowane, gdyby nie było to łatwo możnaby przeiterować od elementów n + 1 sprawdzając sumy dwójek, ewentualnie trójek itd...

0

Dla takiego zbioru wejściowego: {8, 1, 1, 1}, dostajemy: {1, 1, 1, 2, 2 , 8, 9, 10, 11} i nie jest prawdą, że ostatni minus przedostatni daje pierwszy element zbioru wejściowego (11 - 10 != 8). Byłoby tak, gdyby A był nieposortowany.

0

Skoro kolejność ma znaczenie, to dane wejściowe nie są zbiorem, ale ciągiem, prawda? I wyjściowe też?

0

W tym przypadku mogłaby także być mapa (1,1,1,8) dająca ten sam zbiór A

lion137 napisał(a):

Dla takiego zbioru wejściowego: {8, 1, 1, 1}, dostajemy: {1, 1, 1, 2, 2 , 8, 9, 10, 11} i nie jest prawdą, że ostatni minus przedostatni daje pierwszy element zbioru wejściowego (11 - 10 != 8). Byłoby tak, gdyby A był nieposortowany.

0

Tak, są to ciągi, nie zbiory

koszalek-opalek napisał(a):

Skoro kolejność ma znaczenie, to dane wejściowe nie są zbiorem, ale ciągiem, prawda? I wyjściowe też?

0
mikewazowski napisał(a):

W tym przypadku mogłaby także być mapa (1,1,1,8) dająca ten sam zbiór A

lion137 napisał(a):

Dla takiego zbioru wejściowego: {8, 1, 1, 1}, dostajemy: {1, 1, 1, 2, 2 , 8, 9, 10, 11} i nie jest prawdą, że ostatni minus przedostatni daje pierwszy element zbioru wejściowego (11 - 10 != 8). Byłoby tak, gdyby A był nieposortowany.

Skoro tak, to zadanie jest niejednoznaczne, skąd ono pochodzi?

0

Zadanie jest chyba jednoznaczne, jeśli przyjąć, że nie chodzi jednak o ciągi, ale o multizbiory -- wtedy wszystko się zgadza.

0
koszalek-opalek napisał(a):

Zadanie jest chyba jednoznaczne, jeśli przyjąć, że nie chodzi jednak o ciągi, ale o multizbiory -- wtedy wszystko się zgadza.

W multizbiorze kolejnośc elementów nie jest istotna, a tutaj jest.

0

bioinformatyczny problem mapowania częściowym trawieniem

lion137 napisał(a):
mikewazowski napisał(a):

W tym przypadku mogłaby także być mapa (1,1,1,8) dająca ten sam zbiór A

lion137 napisał(a):

Dla takiego zbioru wejściowego: {8, 1, 1, 1}, dostajemy: {1, 1, 1, 2, 2 , 8, 9, 10, 11} i nie jest prawdą, że ostatni minus przedostatni daje pierwszy element zbioru wejściowego (11 - 10 != 8). Byłoby tak, gdyby A był nieposortowany.

Skoro tak, to zadanie jest niejednoznaczne, skąd ono pochodzi?

0
mikewazowski napisał(a):

bioinformatyczny problem mapowania częściowym trawieniem

lion137 napisał(a):
mikewazowski napisał(a):

W tym przypadku mogłaby także być mapa (1,1,1,8) dająca ten sam zbiór A

lion137 napisał(a):

Dla takiego zbioru wejściowego: {8, 1, 1, 1}, dostajemy: {1, 1, 1, 2, 2 , 8, 9, 10, 11} i nie jest prawdą, że ostatni minus przedostatni daje pierwszy element zbioru wejściowego (11 - 10 != 8). Byłoby tak, gdyby A był nieposortowany.

Skoro tak, to zadanie jest niejednoznaczne, skąd ono pochodzi?

To nam nic nie mówi, chodzi o sam problem, czy zbiór ma być posortowany czy nie? A może założenia sa takie, że suma elementów zbioru wejściowego bez pierwszego, jest zawsze druga najwieksza, po sumie wszystkich?

0

treść zadania:
"Należy odtworzyć obraz (mapę) miejsc restrykcyjnych w badanym fragmencie na podstawie wyników tego eksperymentu, czyli takie rozmieszczenie cięć, że odległości pomiędzy wszystkimi parami cięć (a także końcami fragmentu DNA) pokryją się z multizbiorem A.
Przykład: A = {2, 3, 3, 4, 6, 6, 7, 8, 9, 9, 11, 12, 15, 15, 18}. Mapa = (3, 4, 2, 6, 3). Należy zaimplementować algorytm dokładny (przeszukiwanie z nawrotami, o złożoności wykładniczej) realizujący następujące czynności:
− wczytanie z pliku multizbioru A
− skonstruowanie mapy restrykcyjnej zgodnej z podanym multizbiorem (wystarczy jedna z możliwych map);
− wypisanie rezultatu na wyjściu w sposób czytelny dla użytkownika; w razie braku rozwiązania (gdyby instancja zawierała błędy) użytkownik powinien zostać poinformowany odpowiednim komunikatem.
Plik tekstowy zawierający instancję ma składać się z jednego wiersza z sekwencją liczb naturalnych oddzielonych spacjami. Aby nie przekazywać programowi informacji o poprawnym uporządkowaniu odcinków, wartości w pliku powinny wystąpić w innej kolejności niż w rozwiązaniu"

lion137 napisał(a):
mikewazowski napisał(a):

bioinformatyczny problem mapowania częściowym trawieniem

lion137 napisał(a):
mikewazowski napisał(a):

W tym przypadku mogłaby także być mapa (1,1,1,8) dająca ten sam zbiór A

lion137 napisał(a):

Dla takiego zbioru wejściowego: {8, 1, 1, 1}, dostajemy: {1, 1, 1, 2, 2 , 8, 9, 10, 11} i nie jest prawdą, że ostatni minus przedostatni daje pierwszy element zbioru wejściowego (11 - 10 != 8). Byłoby tak, gdyby A był nieposortowany.

Skoro tak, to zadanie jest niejednoznaczne, skąd ono pochodzi?

To nam nic nie mówi, chodzi o sam problem, czy zbiór ma być posortowany czy nie? A może założenia sa takie, że suma elementów zbioru wejściowego bez pierwszego, jest zawsze druga najwieksza, po sumie wszystkich?

0

Rozumiem ze elementy ciagu moga byc ujemne? Jakby byly tylko dodatnie to zadanie bylo by trywialne (wystarczylo by wybrac n najmniejszych elementow - te elementy skladaja sie na czynniki pozostalych elementow mapy A).

0

nie mogą być ujemne, ale najmniejsze elementy A niekoniecznie musza utworzyć mape, przykład:
mapa = {2,15,4,2}
daje nam A = {2,2,4,15,17,19,6,21,21,23} co po posortowaniu A = {2,2,4,6,15,17,19,21,21,23} dawałoby jako elementy mapy 2,2,4 oraz 6 - czyli błędnie.

Trzezwy Karp napisał(a):

Rozumiem ze elementy ciagu moga byc ujemne? Jakby byly tylko dodatnie to zadanie bylo by trywialne (wystarczylo by wybrac n najmniejszych elementow - te elementy skladaja sie na czynniki pozostalych elementow mapy A).

0

W pierwszym poscie napisales ze w sklad zbioru A wchodza wszystkie elementy mapy. Tak wiec jak elementy sa dodatnie to znaczy ze te najmniejsze ze zbioru A tworza mape.

0
import math
import collections

def recCreateMap(M, n, A, available, cnt):
    if len(M) == n:
        s = collections.Counter(cnt)
        base = 0
        for i in range(len(M)):
            sliding = base
            base += M[i]
            for j in range(i, len(M)):
                sliding += M[j]
                if sliding not in s or s[sliding] <= 0:
                    return None
                s[sliding] -= 1
                sliding -= M[j-i]
        return M
    else:
        for i in range(len(A)):
            if available[i]:
                e = abs(M[-1]-A[i])
                if e > 0:
                    M.append(e)
                    available[i] = False
                    res = recCreateMap(M, n, A, available, cnt)
                    if res is not None: return res
                    available[i] = True
                    M.pop()
            

def createMap(A):
    n = 0.5*(math.sqrt(1+8*len(A))-1)
    M = [A[-1] - A[-2]]
    available = [True]*len(A)
    available[A.index(M[-1])] = False
    cnt = collections.Counter(A)
    return recCreateMap(M, n, A, available, cnt)
    
print(createMap([2,2,4,15,17,19,6,21,21,23]))
print(createMap([2, 3, 3, 4, 6, 6, 7, 8, 9, 9, 11, 12, 15, 15, 18]))
0

działa jak trzeba, przetestowałam na wielu przykładach, także super, ale mógłbyś mi wytłumaczyć kilka rzeczy jako że napisałeś w pythonie, z którym znam się tylko trochę? (zakomentowałam w kodzie)

Trzeźwy Karp napisał(a):
import math
import collections

def recCreateMap(M, n, A, available, cnt):
    if len(M) == n:
        s = collections.Counter(cnt) 
        base = 0
        for i in range(len(M)):
            sliding = base
            base += M[i] 
            for j in range(i, len(M)):
                sliding += M[j]
                if sliding not in s or s[sliding] <= 0:
                    return None
                s[sliding] -= 1 // co dzieje się w tej linijce - s jest licznikiem ile razy sprawdziliśmy daną sumę?
                sliding -= M[j-i] // oraz co się dzieje w tej 
        return M
    else:
        for i in range(len(A)):
            if available[i]:
                e = abs(M[-1]-A[i]) // e to różnica między ostatnim elementem mapy a aktualnie sprawdzanym z A? 
                if e > 0:
                    M.append(e)
                    available[i] = False
                    res = recCreateMap(M, n, A, available, cnt)
                    if res is not None: return res
                    available[i] = True
                    M.pop()
            

def createMap(A):
    n = 0.5*(math.sqrt(1+8*len(A))-1)
    M = [A[-1] - A[-2]]
    available = [True]*len(A)
    available[A.index(M[-1])] = False
    cnt = collections.Counter(A)
    return recCreateMap(M, n, A, available, cnt)
    
print(createMap([2,2,4,15,17,19,6,21,21,23]))
print(createMap([2, 3, 3, 4, 6, 6, 7, 8, 9, 9, 11, 12, 15, 15, 18]))
0

// e to różnica między ostatnim elementem mapy a aktualnie sprawdzanym z A?
w sumie to powinno byc A[i]-M[-1] bez tego abs.

// s jest licznikiem ile razy sprawdziliśmy daną sumę?
Tak, bo w koncu A to multizbior a nie zwykly zbior

0

ok, przepisuje twój kod na C++, bo takie są wymogi zadania i nie rozumiem jeszcze tych dwóch linijek - w razie jeśli liczbę można dodać do mapy - czyli res != None zwracamy res - czyli co właściwie się dzieje po linijce return res - wracamy całkiem na początek funkcji i sprawdzamy kolejną liczbę?

res = recCreateMap(M, n, A, available, cnt)
  if res is not None: return res

0

Tak, jezeli wywolanie funkcji stwierdzilo, ze taka kombinacja nie pasuje, to sprobuj kolejna kombinacje.

0

utknęłam na pewnym etapie gdzie zwraca mapę która tworzy tylko część sum z A i nie potrafię wykminić co jest nie tak, a jako że to ty napisałeś i najlepiej wiesz o co biega w kodzie - mógłbyś spojrzeć w mój kod i spróbować coś doradzić, czy nawet go tutaj nie wrzucać?

Trzeźwy Karp napisał(a):

Tak, jezeli wywolanie funkcji stwierdzilo, ze taka kombinacja nie pasuje, to sprobuj kolejna kombinacje.

0

Wrzucic zawsze mozesz...

0
bool mapowanie(int k,bool *uzyto,int *hm,int maxi)
{

int *counter = new int [maxi];
for (int i=0;i<maxi;i++)
{
    counter[i] = hm[i];
}
TU:
int base,sliding,e;
bool res;

if (mapa.size() == k)
{
    base = 0;
    for (int i=0;i<mapa.size();i++)
    {
        sliding = base;
        base += mapa[i];
        for (int j=i;j<mapa.size();j++)
        {
            sliding += mapa[j];
            if (counter[sliding] == 0)
                return false;
            counter[sliding] -= 1;
            sliding -= mapa[j-i];
        }
    }
    return true;
}
else for (int i=0;i<A.size();i++)
{
    if (uzyto[i] == false)
    {
        e = A[i] - mapa.back();
        if (e > 0)
        {
            mapa.push_back(A[i]); // e
            uzyto[i] = true;
            res = mapowanie(k,uzyto,hm,maxi);
            if (res == false)
            {
                return false; // break?
            }
           uzyto[i] = false;
           mapa.pop_back();
        }
    }
}
}

void nieuzyte(int licznosc, bool *odwiedzone)
{
    for (int i=0; i<licznosc; i++)
    {
        odwiedzone[i] = false;
    }
}

int main()
{
    bool *uzyte = new bool [licznosc]; // licznosc wyliczana wczesniej
    nieuzyte(licznosc,uzyte);
    int maxi = A[0];
    for (int i=0;i<A.size();i++)
    {
        if (A[i] > maxi)
            maxi = A[i];
    }
    maxi += 1;
    int *counter = new int [maxi]; // to samo co collections.Counter(A) w pythonie
    for (int i=0;i<maxi;i++)
    {
        counter[i] = 0;
    }
    for (int i=0;i<A.size();i++)
    {
        int hm = A[i];
        counter[hm]++;
    }


        int pierwszy_w_mapie = pierwszy_element(licznosc);
        mapa.push_back(pierwszy_w_mapie);

        for (int i=0; i<A.size(); i++)
        {
            if(A[i] == pierwszy_w_mapie )
            {
                uzyte[i] = true;
                break;
            }
        }


        mapowanie(k,uzyte,counter,maxi);
        wyswietl_mape();


return 0;
    }

```cpp








> ##### [Trzeźwy Karp napisał(a)](https://4programmers.net/Forum/1451400):
> Wrzucic zawsze mozesz...
0

Pierwsze co widze to:
mapa.push_back(A[i]); // e
a powinno byc mapa.push_back(e)

0

sprawdziłam - gdy dodaje e to do mapy dodają się liczby których nie ma w ogóle w zbiorze A, przetestowałam też w twoim kodzie - zamiana e na A[i] daje takie same, prawidłowe wyniki

Trzeźwy Karp napisał(a):

Pierwsze co widze to:
mapa.push_back(A[i]); // e
a powinno byc mapa.push_back(e)

0

Tu masz rozwiazanie w Javie, moze bedzie troche latwiejsze do przeniesienia w C++

import java.util.LinkedList;
import static java.lang.Math.sqrt;

public class Solver {

    private static boolean checkLength(int n,int len)
    {
        if(n*(n+1) == 2*len) return true;
        else return false;
    }

    private static boolean computeElements(int[] v, LinkedList<Integer> al, int pos, int n) {

        int from = pos*(pos+1)/2;
        int to = from + pos + 1;

        Integer diff = v[v.length-(from+1)]-v[pos];
        if(al.contains(diff)) {
            al.remove(diff);
            v[v.length-(to+1)] = diff;
        }
        else return false;

        int index = pos;
        int inc = n-1;
        for(int p = pos; p > 0; p--, inc--) {
            Integer sum = v[index-1]+v[pos];
            if(al.contains(sum)) {
                index += inc;
                al.remove(sum);
                v[index]=sum;
            }
            else return false;
        }
        return true;
    }

    private static boolean fillFrom(int[] v, LinkedList<Integer> al, int pos, int n) {

        for(Integer element : al) {
            LinkedList<Integer> alCopy = new LinkedList<>(al);
            alCopy.remove(element);
            v[pos] = element;
            if(!computeElements(v,alCopy,pos,n)) {
                continue;
            }
            if(pos == n-2) return true;
            if(fillFrom(v, alCopy, pos + 1, n)) return true;
        }
        return false;
    }

    public static boolean solve(int[] A) {

        int len = A.length;
        int n = (int) sqrt(len*2);
        if(!checkLength(n,len)) {
            System.out.println("Incorrect length of the set");
            return false;
        }

        LinkedList<Integer> al = new LinkedList<Integer>() {{ for (int i : A) add(i); }};
        int[] v = new int[al.size()];
        v[v.length-1] = al.remove(al.size()-1);
        v[v.length-2] = al.remove(al.size()-1);
        v[0] = v[v.length-1] - v[v.length-2];
        al.remove(new Integer(v[0]));

        if(fillFrom(v, al, 1, n)) {
            System.out.print("Solution: ");
            for(int i=0; i<n; i++) {
                System.out.print(v[i]+ " ");
            }
            System.out.println();
            return true;
        } else {
            System.out.println("Set can't be solved");
            return false;
        }
    }
}

Wywolanie:

public class Main {

    public static void main(String[] args) {

        int[] A = {1, 2, 3, 7, 8, 8, 10, 11, 13, 14, 15, 16, 17, 19, 21, 23, 24, 25, 26, 27, 29, 32, 37, 39, 40, 40, 47, 48};
        int[] B = {2,2,4,6,15,17,19,21,21,23};
        int[] C = {2, 3, 3, 4, 6, 6, 7, 8, 9, 9, 11, 12, 15, 15, 18};

        Solver s = new Solver();
        s.solve(A);
        s.solve(B);
        s.solve(C);
    }
}
0

niestety nie znam javy, ale dzięki za chęci!

GutekSan napisał(a):

Tu masz rozwiazanie w Javie, moze bedzie troche latwiejsze do przeniesienia w C++

import java.util.LinkedList;
import static java.lang.Math.sqrt;

public class Solver {

    private static boolean checkLength(int n,int len)
    {
        if(n*(n+1) == 2*len) return true;
        else return false;
    }

    private static boolean computeElements(int[] v, LinkedList<Integer> al, int pos, int n) {

        int from = pos*(pos+1)/2;
        int to = from + pos + 1;

        Integer diff = v[v.length-(from+1)]-v[pos];
        if(al.contains(diff)) {
            al.remove(diff);
            v[v.length-(to+1)] = diff;
        }
        else return false;

        int index = pos;
        int inc = n-1;
        for(int p = pos; p > 0; p--, inc--) {
            Integer sum = v[index-1]+v[pos];
            if(al.contains(sum)) {
                index += inc;
                al.remove(sum);
                v[index]=sum;
            }
            else return false;
        }
        return true;
    }

    private static boolean fillFrom(int[] v, LinkedList<Integer> al, int pos, int n) {

        for(Integer element : al) {
            LinkedList<Integer> alCopy = new LinkedList<>(al);
            alCopy.remove(element);
            v[pos] = element;
            if(!computeElements(v,alCopy,pos,n)) {
                continue;
            }
            if(pos == n-2) return true;
            if(fillFrom(v, alCopy, pos + 1, n)) return true;
        }
        return false;
    }

    public static boolean solve(int[] A) {

        int len = A.length;
        int n = (int) sqrt(len*2);
        if(!checkLength(n,len)) {
            System.out.println("Incorrect length of the set");
            return false;
        }

        LinkedList<Integer> al = new LinkedList<Integer>() {{ for (int i : A) add(i); }};
        int[] v = new int[al.size()];
        v[v.length-1] = al.remove(al.size()-1);
        v[v.length-2] = al.remove(al.size()-1);
        v[0] = v[v.length-1] - v[v.length-2];
        al.remove(new Integer(v[0]));

        if(fillFrom(v, al, 1, n)) {
            System.out.print("Solution: ");
            for(int i=0; i<n; i++) {
                System.out.print(v[i]+ " ");
            }
            System.out.println();
            return true;
        } else {
            System.out.println("Set can't be solved");
            return false;
        }
    }
}

Wywolanie:

public class Main {

    public static void main(String[] args) {

        int[] A = {1, 2, 3, 7, 8, 8, 10, 11, 13, 14, 15, 16, 17, 19, 21, 23, 24, 25, 26, 27, 29, 32, 37, 39, 40, 40, 47, 48};
        int[] B = {2,2,4,6,15,17,19,21,21,23};
        int[] C = {2, 3, 3, 4, 6, 6, 7, 8, 9, 9, 11, 12, 15, 15, 18};

        Solver s = new Solver();
        s.solve(A);
        s.solve(B);
        s.solve(C);
    }
}
0

Wklejam znacznie wydajniejsza wersje, z przycieciami przestrzeni poszukiwan co znacznie redukuje czas wyszukiwania

import math
import collections
import copy

def recCreateMap(M, cnt, ends):
    elems = tuple(cnt.elements())
    if len(elems) == 0:
        return M
    else:
        for a in elems:
            e = a-M[-1]
            if e > 0 and e in cnt:
                accept = True
                newCnt = collections.Counter(cnt)
                newEnds = copy.deepcopy(ends)
                for k, l in ends.items():
                    for v in l:
                        if k == 0 or len(M) == v+1:
                            if k+e not in newCnt:
                                accept = False
                                break
                            newEnds[k+e].append(len(M))
                            newCnt[k+e] -= 1
                            if newCnt[k+e] == 0: 
                                del newCnt[k+e]
                if accept:
                    M.append(e)
                    res = recCreateMap(M, newCnt, newEnds)
                    if res is not None: return res
                    M.pop()
            

def createMap(A):
    M = [A[-1] - A[-2]]
    cnt = collections.Counter(A)
    cnt[M[-1]] -= 1
    ends = collections.defaultdict(list)
    ends[0] = [0]
    ends[M[-1]] = [0]
    return recCreateMap(M, cnt, ends)
    
print(createMap([2,2,4,15,17,19,6,21,21,23]))
print(createMap([2,3,3,4,6,6,7,8,9,9,11,12,15,15,18]))
print(createMap([1, 2, 3, 7, 8, 8, 10, 11, 13, 14, 15, 16, 17, 19, 21, 23, 24, 25, 26, 27, 29, 32, 37, 39, 40, 40, 47, 48]))
0

czym defaultdict różni się od zwykłego słownika?

 ends = collections.defaultdict(list)
Trzeźwy Karp napisał(a):

Wklejam znacznie wydajniejsza wersje, z przycieciami przestrzeni poszukiwan co znacznie redukuje czas wyszukiwania

import math
import collections
import copy

def recCreateMap(M, cnt, ends):
    elems = tuple(cnt.elements())
    if len(elems) == 0:
        return M
    else:
        for a in elems:
            e = a-M[-1]
            if e > 0 and e in cnt:
                accept = True
                newCnt = collections.Counter(cnt)
                newEnds = copy.deepcopy(ends)
                for k, l in ends.items():
                    for v in l:
                        if k == 0 or len(M) == v+1:
                            if k+e not in newCnt:
                                accept = False
                                break
                            newEnds[k+e].append(len(M))
                            newCnt[k+e] -= 1
                            if newCnt[k+e] == 0: 
                                del newCnt[k+e]
                if accept:
                    M.append(e)
                    res = recCreateMap(M, newCnt, newEnds)
                    if res is not None: return res
                    M.pop()
            

def createMap(A):
    M = [A[-1] - A[-2]]
    cnt = collections.Counter(A)
    cnt[M[-1]] -= 1
    ends = collections.defaultdict(list)
    ends[0] = [0]
    ends[M[-1]] = [0]
    return recCreateMap(M, cnt, ends)
    
print(createMap([2,2,4,15,17,19,6,21,21,23]))
print(createMap([2,3,3,4,6,6,7,8,9,9,11,12,15,15,18]))
print(createMap([1, 2, 3, 7, 8, 8, 10, 11, 13, 14, 15, 16, 17, 19, 21, 23, 24, 25, 26, 27, 29, 32, 37, 39, 40, 40, 47, 48]))

1 użytkowników online, w tym zalogowanych: 0, gości: 1