W dniu 18.11.2019 o 23:40, g...@g...com pisze:
>> [[1,10],[7,3],[10],[100],[5,6]]
> Trochę poprawiłem nazwy i formatowanie, może teraz będzie nieco czytelniejsze:
> https://rextester.com/CRWPJS53169

Wyniki daje dobre.
Trzeba by przeanalizować, jakie znaczenie ma ++ ?
jest tu jakiś sposób rekurencyjny
grouped [] [] = []
grouped [] g = [g]
Te dwa powyżej rozumiem
a
grouped (h:t) g
| (cond (g++[h])) = [g++[h]]++(grouped t [])
grouped (h:t) g = grouped t (g++[h])

?

do góry

W dniu wtorek, 19 listopada 2019 13:52:06 UTC+1 użytkownik Borneq napisał:

> >> [[1,10],[7,3],[10],[100],[5,6]]
> > Trochę poprawiłem nazwy i formatowanie, może teraz będzie nieco czytelniejsze:
> > https://rextester.com/CRWPJS53169
>
> Wyniki daje dobre.
> Trzeba by przeanalizować, jakie znaczenie ma ++ ?

++ to sklejanie list:

[1,2]++[3,4] daje [1,2,3,4]

Niestety w przypadku języków funkcyjnych dopisywanie elementu na koniec listy jest
raczej kosztowne. No ale to szczegół


> jest tu jakiś sposób rekurencyjny

Jest rekurencyjny, ale to prosta rekurencja, którą można łatwo zamienic na pętlę.
Jakby co, to napisałem rozwiązanie rekurencyjne w Pythonie.

Wariant iteracyjny wygląda tak:

def igroups(l, cond):
result = []
group = []
for x in l:
group += [x]
if cond(group):
result += [group]
group = []
if group:
result += [group]
return result


> grouped [] [] = []
> grouped [] g = [g]
> Te dwa powyżej rozumiem
> a
> grouped (h:t) g
> | (cond (g++[h])) = [g++[h]]++(grouped t [])
> grouped (h:t) g = grouped t (g++[h])
>
> ?

W pierwszym przypadku jest tzn. "pattern guard", tzn. jeżeli funkcja "cond" dla
argumentu g++[h] zwróci True, to zwracamy [g++[h]] ++ (grouped t []), albo innymi
słowy - zamykamy bieżącą grupę z dopisanym bieżącym elementem i tworzymy nową pustą
grupę, którą będziemy przetwarzać na pozostałych elementach listy.

Jeżeli "cond" nie jest spełnione, to dodajemy bieżący element do bieżącej grupy i
przetwarzamy resztę listy.

Tutaj jest Pythonowa wersja, w której umieściłem Haskellowe patterny i guardy w
komentarzach

def groups(l, cond):
def group(l, g):
if l: ### grouped (h:t) g -- lista niepusta
h, *t = l
if cond(g+[h]): ### | (cond (g++[h])) -- warunek spelniony
return [g+[h]]+group(t, [])
return group(t, g+[h]) ### -- warunek niespelniony
if g:
return [g] ### grouped [] g -- grupa jest niepusta
return [] ### grouped [] [] -- pusta grupa
return group(l, [])


Oba warianty możesz potestować tutaj:
https://rextester.com/FCY59693

do góry

W dniu 19.11.2019 o 17:11, g...@g...com pisze:
> Tutaj jest Pythonowa wersja, w której umieściłem Haskellowe patterny i guardy w
komentarzach
> return group(t, g+[h]) ### -- warunek niespelniony
> if g:
> return [g] ### grouped [] g -- grupa jest niepusta
> return [] ### grouped [] [] -- pusta grupa
> return group(l, [])

To jest jakaś rekurencja ogonowa, którą można przenieść na pętlę nie
zajmując stosu?

do góry

W dniu 19.11.2019 o 17:11, g...@g...com pisze:
> Tutaj jest Pythonowa wersja, w której umieściłem Haskellowe patterny i guardy w
komentarzach

Wielkie dzięki, Python da już radę być przerobiony na C++

do góry

W dniu wtorek, 19 listopada 2019 17:37:28 UTC+1 użytkownik Borneq napisał:

> > Tutaj jest Pythonowa wersja, w której umieściłem Haskellowe patterny i guardy w
komentarzach
> > return group(t, g+[h]) ### -- warunek niespelniony
> > if g:
> > return [g] ### grouped [] g -- grupa jest niepusta
> > return [] ### grouped [] [] -- pusta grupa
> > return group(l, [])
>
> To jest jakaś rekurencja ogonowa, którą można przenieść na pętlę nie
> zajmując stosu?

Nie, w tym przypadku rekurencja nie jest ogonowa, bo jedno z wywołań rekurencyjnych
jest zagnieżdżone w wywołanie innej funkcji (sklejania list).
Chodzi konkretnie o linię:

return [g+[h]]+group(t, [])

Typowo jeśli chcielibyśmy przekształcić taką rekurencję w rekurencję ogonową,
musielibyśmy stworzyć dodatkowy argument reprezentujący wynik.

Możemy tak zrobić, jeśli strukutra rekurencji jest liniowa (albo inaczej:
nie-drzewiasta). Wersja Pythonowa zapisana z rekurencją ogonową wyglądałaby tak:

def trgroups(l, cond):
def group(l, g, out):
if l:
h, *t = l
if cond(g+[h]):
return group(t, [], out+[g+[h]])
return group(t, g+[h], out)
if g:
return out+[g]
return out
return group(l, [], [])

Takie coś rzeczywiście nie powinno zajmować stosu w implementacjach optymalizujących
rekurencję ogonową (do których Pythony raczej się nie zaliczają)

Tutaj link:
https://rextester.com/FCY59693

do góry

On Monday, November 18, 2019 at 2:09:47 PM UTC+1, Borneq wrote:
> Mam liczby 1,5,7,10,100,5,6,
> jak zrobić grupy o co najmniej sumie 10, nie zmieniając kolejności tak jak:
> (1,5,7),(10),(100),(5,6),
> zamiast liczb mogą być długości stringów,
> mogę najprościej:
> vector<wstring> vec;
> vector<wstring> veclongs;
>
> int n = 0;
> for (int i = 0; i < vec.size(); i++)
> {
> if (i == 0 || vec[i].length() > 10)
> {
> veclongs.push_back(vec[i]);
> n++;
> }
> else veclongs.back() = veclongs.back() + vec[i];
> }
> return veclongs;
>
> Jedna wada to i==0 bo inaczej nie da rady veclongs.back()
> co gdy pierwszy będzie mały np 5 a pozostałe wystarczajace?
> np: 5,10,10,10, - bez grupowania
> a trzeba (5,10),10,10
> Jak to zrobić, niby prosto bo bez zmiany kolejności

A w jednej grupie mogą być opuszczenia wyrazów, czy nie?
Jak nie mogą, czyli jak muszą być kolejne, to tak:

#include <QTextStream>
#include <QTextCodec>
#include <QByteArray>
#include <QRegExp>
#include <QStringList>

static void groups(
QTextStream &sout ,
const QStringList &words ,
const int start ,
const int minLen ,
QStringList &stack
) {
bool found = false;
for( int i=start ; i<words.size() ; i++ ) {
int len = 0;
for( int j=i ; j<words.size() ; j++ ) {
len += words[j].size();
if( len < minLen ) {
continue;
}
found = true;
stack.push_back( words.mid(i,j-i+1).join('|') ) ;
groups( sout , words , j+1 , minLen , stack );
stack.pop_back();
}
}
if( ! found && stack.size() > 0 ) {
sout << stack.join(", ") << endl;
}
}

int main(int argc, char *argv[]) {
(void)argc;
(void)argv;
QTextStream sinp(stdin);
QTextStream sout(stdout);
sinp.setCodec("UTF-8");
sout.setCodec("UTF-8");
const int minLen = sinp.readLine().toInt();
const QString line = sinp.readLine();
const QStringList words = line.split( QRegExp("\\s+") , QString::SkipEmptyParts
);
QStringList stack;
groups( sout , words , 0 , minLen , stack );
return 0;
}

8
aaaa bbb ccc ddd eee fffffffff gg
aaaa|bbb|ccc, ddd|eee|fffffffff
aaaa|bbb|ccc, ddd|eee|fffffffff|gg
aaaa|bbb|ccc, eee|fffffffff
aaaa|bbb|ccc, eee|fffffffff|gg
aaaa|bbb|ccc, fffffffff
aaaa|bbb|ccc, fffffffff|gg
aaaa|bbb|ccc|ddd, eee|fffffffff
aaaa|bbb|ccc|ddd, eee|fffffffff|gg
aaaa|bbb|ccc|ddd, fffffffff
aaaa|bbb|ccc|ddd, fffffffff|gg
aaaa|bbb|ccc|ddd|eee, fffffffff
aaaa|bbb|ccc|ddd|eee, fffffffff|gg
aaaa|bbb|ccc|ddd|eee|fffffffff
aaaa|bbb|ccc|ddd|eee|fffffffff|gg
bbb|ccc|ddd, eee|fffffffff
bbb|ccc|ddd, eee|fffffffff|gg
bbb|ccc|ddd, fffffffff
bbb|ccc|ddd, fffffffff|gg
bbb|ccc|ddd|eee, fffffffff
bbb|ccc|ddd|eee, fffffffff|gg
bbb|ccc|ddd|eee|fffffffff
bbb|ccc|ddd|eee|fffffffff|gg
ccc|ddd|eee, fffffffff
ccc|ddd|eee, fffffffff|gg
ccc|ddd|eee|fffffffff
ccc|ddd|eee|fffffffff|gg
ddd|eee|fffffffff
ddd|eee|fffffffff|gg
eee|fffffffff
eee|fffffffff|gg
fffffffff


fffffffff|gg

do góry