Sprawdzenie wszystkich możliwości.

Mam 4 budynki. Każdy budynek może mieć X poziomów założmy, że jest to 10.
Każdy z 4 budynków mogę budować w jakiej kolejności chce. Teraz moje zadanie polega na zbudowaniu algorytmu, który rozbuduje te 4 budynki do maksymalnych poziomów czyli w tym przypadku 10.
W zwykłych pętlach się tego nie zrobi. Ma ktoś pomysł jak to zrobić?

Przykład jednego rozbudowania dla 3 budynków o 3 poziomach.
1 1 1
2 1 1
3 1 1
3 1 2
3 1 3
3 2 1
3 2 2
3 2 3
3 3 1
3 3 2
3 3 3

Jest to jedna z wielu możliwości, tylko jak wygenerować wszystkie możliwe?

Przykład jednego rozbudowania dla 3 budynków o 3 poziomach.
1 1 1
2 1 1
3 1 1
3 1 2
3 1 3
3 2 3
3 3 3

Tak powinien brzmieć przykład, moja pomyłka.

Twojego opisu problemu nie rozumiem. Domyślam się, że chodzi o zagnieżdżone pętle for, ale głębokość zagnieżdżenia poznasz dopiero w czasie wykonywania programu. Dobrze się domyślam?

Mam 4 budynki, każdy budynek ma 10 poziomów. Chce każdy budynek rozwinać od budynki 1 do 10. W zależności od kolejności rozwijania mam różne wyniki. Np. 1 budnek 1 poziom, 2 budynek 1 poziom, 1 budynek 2 poziom, 3 budynk 1 poziom, 1 budynek 3 poziom, itd. Pętle for tutaj nie pomogą.

wydaje mi się że chodzi o zastosowanie rekurencji, tylko tak jak kolega, ja także nie rozumiem o co dokładnie chodzi.

Budujesz graf skierowany (cykli nie będzie, bo nie przewidujesz burzenia pięter) i wyświetlasz wszystkie ścieżki jakie w nim są.

masz i zacznij się uczyć https://ideone.com/VlQi6e

abrakadaber napisał(a):

masz i zacznij się uczyć https://ideone.com/VlQi6e

No tylko ty dałeś to co ja dałem w przykładzie, a w przykładzie jest podana tylko jedna możliwość a ja chce tych możliwości wygenerować tyle ile się da.

w_s_l_s napisał(a):

abrakadaber napisał(a):

masz i zacznij się uczyć https://ideone.com/VlQi6e

No tylko ty dałeś to co ja dałem w przykładzie, a w przykładzie jest podana tylko jedna możliwość a ja chce tych możliwości wygenerować tyle ile się da.

to może zacznij zadawać PRECYZYJNE pytania a jak podajesz przykład to niech on DOKŁADNIE ODZWIERCIEDLA WYNIK JAKI CHCESZ UZYSKAĆ!
A czy można w połowie przestać budować budynek a i zacząć budynek b?

abrakadaber napisał(a):

w_s_l_s napisał(a):

abrakadaber napisał(a):

masz i zacznij się uczyć https://ideone.com/VlQi6e

No tylko ty dałeś to co ja dałem w przykładzie, a w przykładzie jest podana tylko jedna możliwość a ja chce tych możliwości wygenerować tyle ile się da.

to może zacznij zadawać PRECYZYJNE pytania a jak podajesz przykład to niech on DOKŁADNIE ODZWIERCIEDLA WYNIK JAKI CHCESZ UZYSKAĆ!
A czy można w połowie przestać budować budynek a i zacząć budynek b?

Tak można, żeby pokazać dokładny wynik z przykładu musiałbym napisać program który właśnie chce napisać. Myślałem, że pisałem o możliwości przerwania budowania danego budynki żeby zaczać budowac budynek inny.

ile jesteś w stanie dać za rozwiązanie?
mała próbka:

• dla ilość budynków: 3 ilość pięter: 6
  Wynik:

6  6  6  
6  6  5  
6  6  4  
6  6  3  
6  6  2  
6  6  1  
6  5  1  
6  4  1  
6  3  1  
6  2  1  
6  1  1  
5  1  1  
4  1  1  
3  1  1  
2  1  1  
1  1  1  
 
6  6  6  
6  6  5  
6  6  4  
6  6  3  
6  6  2  
6  5  2  
6  5  1  
6  4  1  
6  3  1  
6  2  1  
6  1  1  
5  1  1  
4  1  1  
3  1  1  
2  1  1  
1  1  1

plik tekstowy w takim formacie waży 129MB

*dla ilość budynków: 4 ilość pięter: 4
Wynik:

4  4  4  4  
4  4  4  3  
4  4  4  2  
4  4  4  1  
4  4  3  1  
4  4  2  1  
4  4  1  1  
4  3  1  1  
4  2  1  1  
4  1  1  1  
3  1  1  1  
2  1  1  1  
1  1  1  1  
 
4  4  4  4  
4  4  4  3  
4  4  4  2  
4  4  3  2  
4  4  3  1  
4  4  2  1  
4  4  1  1  
4  3  1  1  
4  2  1  1  
4  1  1  1  
3  1  1  1  
2  1  1  1  
1  1  1  1

plik tekstowy w takim formacie waży 65MB
Oba w załączniku. Przy dla ilość budynków: 4 ilość pięter: 10 u mnie się wywala z Out of memory :p

abrakadaber napisał(a):

ile jesteś w stanie dać za rozwiązanie?
mała próbka:

• dla ilość budynków: 3 ilość pięter: 6
  Wynik:
  plik tekstowy w takim formacie waży 65MB
  Oba w załączniku. Przy dla ilość budynków: 4 ilość pięter: 10 u mnie się wywala z Out of memory :p

Nawet nie wiem czy twoje rozwiązanie działa, nie jestem w stanie zapłacić. Ogólnie ogarnałem, że dla moich danych liczba rozwiązań będzie wynosiła liczbą z 72 cyframi a gdy jedno rozwiązanie trochę waży to nie przetworze tego.

Na samą liczbę kombinacji takiego przypadku jest prosty wzór, który można znaleźć tutaj:
http://en.wikipedia.org/wiki/Permutation#Permutations_of_multisets

Gdyby budować n budynków o p poziomach to wzór na liczbę wszystkich kombinacji wygląda tak:

N_n,p = (n*p)!/(p!ⁿ)

Więc np. dla podanego zadania liczba ta by wynosiła (p mniejsze jest o 1 bo parter jest już zbudowany):

N_4,9 = (4*9)!/(9!⁴) = 36!/362880⁴ = 21452752266265320000 kombinacji

Z przykładu Abrakadabra mamy:

N_3,5 = (35)!/(5!³) = 15!/120³ = 756756 kombinacji
N_4,3 = (43)!/(3!⁴) = 12!/6⁴ = 369600 kombinacji

thwei11 napisał(a):

Na samą liczbę kombinacji takiego przypadku jest prosty wzór, który można znaleźć tutaj:
http://en.wikipedia.org/wiki/Permutation#Permutations_of_multisets

Gdyby budować n budynków o p poziomach to wzór na liczbę wszystkich kombinacji wygląda tak:

N_n,p = (n*p)!/(p!ⁿ)

Więc np. dla podanego zadania liczba ta by wynosiła (p mniejsze jest o 1 bo parter jest już zbudowany):

N_4,9 = (4*9)!/(9!⁴) = 36!/362880⁴ = 21452752266265320000 kombinacji

Z przykładu Abrakadabra mamy:

N_3,5 = (35)!/(5!³) = 15!/120³ = 756756 kombinacji
N_4,3 = (43)!/(3!⁴) = 12!/6⁴ = 369600 kombinacji

No tylko ja mam 4 budynki po 30 poziomów :) Dane w temacie były przykładowe aby z pomocy uzyskanej mogłbym sobie sam ogarnać.

Dobra, rozwiązanie żeby nie było :p

program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils, Classes;

type
  TPoziom = array of Byte;
  PLisc = ^TLisc;
  TLisc = record
    Korzen: PLisc;
    Liscie: TList;
    Poziom: TPoziom;
    Pietro: Byte;
  end;


var
  ilosc_pieter, ilosc_budynkow: Byte;
  Osiedle: PLisc;

function PoziomToStr(Poziom: TPoziom): string;
var
  i: Integer;
begin
  Result := '';
  for i := 0 to Length(Poziom) - 1 do
    Result := Result + IntToStr(Poziom[i]) + '  ';
end;

function DodajLisc(Lisc: PLisc): PLisc;
var
  i: Integer;
begin
  New(Result);
  if Lisc <> nil then
  begin
    Lisc.Liscie.Add(Result);
    Result.Pietro := Lisc.Pietro + 1;
  end
  else
    Result.Pietro := 1;
  Result.Korzen := Lisc;
  Result.Liscie := TList.Create;
  SetLength(Result.Poziom, ilosc_budynkow);
  for i := 0 to ilosc_budynkow - 1 do
    Result.Poziom[i] := 1;
end;

procedure UsunLisc(Lisc: PLisc);
var
  i: Integer;
begin
  if Lisc = nil then
    Exit;
    
  while Lisc.Liscie.Count > 0 do
  begin
    UsunLisc(Lisc.Liscie.Last);
    Lisc.Liscie.Delete(Lisc.Liscie.Count - 1);
  end;
  Lisc.Liscie.Free;
  SetLength(Lisc.Poziom, 0);
  Dispose(Lisc);
end;

procedure WybudujOsiedle(Lisc: PLisc);
var
  i, j: Byte;
  l: PLisc;
begin
  if Lisc = nil then
    Exit;

  for i := 0 to ilosc_budynkow - 1 do
  begin
    if Lisc.Poziom[i] < ilosc_pieter then
    begin
      l := DodajLisc(Lisc);
      for j := 0 to ilosc_budynkow - 1 do
      begin
        if i = j then
          l.Poziom[j] := Lisc.Poziom[j] + 1
        else
          l.Poziom[j] := Lisc.Poziom[j];
      end;
      WybudujOsiedle(l);
    end;
  end;
end;

procedure WyswietlLiscie(lisc: PLisc; p: Byte);
var
  i: Integer;
  l: PLisc;
begin
  if lisc = nil then
    Exit;

  if lisc.Liscie.Count = 0 then
  begin
    l := lisc;
    WriteLn(' ');
    while l <> nil do
    begin
      Writeln(PoziomToStr(l.Poziom));
      l := l.Korzen;
    end;
  end
  else
    for i := 0 to lisc.Liscie.Count - 1 do
      WyswietlLiscie(lisc.Liscie[i], 0);
end;

var
  l: PLisc;
begin
  Write('Podaj ilosc pieter: ');
  ReadLn(ilosc_pieter);
  Write('Podaj ilosc budynkow: ');
  Readln(ilosc_budynkow);

  Osiedle := DodajLisc(nil);
  WybudujOsiedle(Osiedle);
  WyswietlLiscie(Osiedle, 1);
  UsunLisc(Osiedle);

  Readln;
end.

Pisane pod delphi (użycie TList, dynamicznych tablic), można zoptymalizować zużycie pamięci (zamiast wspomnianego TList użyć dynamicznej tablicy lub listy na wskaźnikach). DodajLisc i UsunLisc to najzwyklejsza implementacja drzewa. WyswietlLiscie szuka najpierw "końców" drzewa (czyli liści ale żeby typy/zmienne są ponazywane tak a nie inaczej to inna sprawa) i potem wyświetla wszystkie etapy budowy idąc aż do korzenia. Całą "magia" dzieje się w procedurze WybudujOsiedle ale to już do rozgryzienia dla pytacza

import itertools


class unique_element:
    def __init__(self,value,occurrences):
        self.value = value
        self.occurrences = occurrences

def perm_unique(elements):
    eset=set(elements)
    listunique = [unique_element(i,elements.count(i)) for i in eset]
    u=len(elements)
    return perm_unique_helper(listunique,[0]*u,u-1)

def perm_unique_helper(listunique,result_list,d):
    if d < 0:
        yield tuple(result_list)
    else:
        for i in listunique:
            if i.occurrences > 0:
                result_list[d]=i.value
                i.occurrences-=1
                for g in  perm_unique_helper(listunique,result_list,d-1):
                    yield g
                i.occurrences+=1
                
                
                
items = ["A", "A", "A", "B", "B", "B"]       
for permutation in perm_unique(items):
    print(permutation)

Łatwo to można przekonwertować na inny wynik taki jak podany w pierwszym poście mimo, że ten jest łatwiejszy i ładniejszy.