🚀 go-pugleaf

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

Potrzebujesz dowolną grupę, jakąś konkretną, wszystkie grupy?

Pozdrawiam

W dniu 18.11.2019 o 15:22, M.M. pisze:
> 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
> 
> Potrzebujesz dowolną grupę, jakąś konkretną, wszystkie grupy?
> 
> Pozdrawiam
> 
Wszystkie, chcę łączyć stringi, aby miały conajmniej jakąś długość.

W dniu poniedziałek, 18 listopada 2019 14:09:47 UTC+1 użytkownik Borneq napisał:
> 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


W Haskellu na szybko:

groups :: [a] -> ([a] -> Bool) -> [[a]]
groups list c = f list []
    where f (h:t) g | (c (g++[h])) = [g++[h]]++(f t [])
          f (h:t) g                = f t (g++[h])
          f  []   g                = []

groups [1,5,7,10,100,5,6] (\x -> (sum x) >= 10)
[[1,5,7],[10],[100],[5,6]]

W dniu poniedziałek, 18 listopada 2019 15:47:23 UTC+1 użytkownik godek...@gmail.com napisał:
> W dniu poniedziałek, 18 listopada 2019 14:09:47 UTC+1 użytkownik Borneq napisał:
> > 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
> 
> 
> W Haskellu na szybko:
> 
> groups :: [a] -> ([a] -> Bool) -> [[a]]
> groups list c = f list []
>     where f (h:t) g | (c (g++[h])) = [g++[h]]++(f t [])
>           f (h:t) g                = f t (g++[h])
>           f  []   g                = []
> 
> groups [1,5,7,10,100,5,6] (\x -> (sum x) >= 10)
> [[1,5,7],[10],[100],[5,6]]

Ewentualnie jakbyś chciał, żeby ostatnia niepełna grupa też trafiała do listy, to wtedy zamiast ostatniego warunku byś musiał napisać:

          f [] [] = []
          f []  g = [g]

On Monday, November 18, 2019 at 3:28:24 PM UTC+1, Borneq wrote:
> W dniu 18.11.2019 o 15:22, M.M. pisze:
> > 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
> > 
> > Potrzebujesz dowolną grupę, jakąś konkretną, wszystkie grupy?
> > 
> > Pozdrawiam
> > 
> Wszystkie, chcę łączyć stringi, aby miały conajmniej jakąś długość.

I tak że jeśli jakiś wyraz był na pozycji np. drugiej, a inny wyraz
na pozycji trzeciej, to po złączeniu nie zamienią się kolejnością, tylko
nadal będzie złączenie drugi+trzeci?

Pozdrawiam

W dniu 18.11.2019 o 16:12, M.M. pisze:
> I tak że jeśli jakiś wyraz był na pozycji np. drugiej, a inny wyraz
> na pozycji trzeciej, to po złączeniu nie zamienią się kolejnością, tylko
> nadal będzie złączenie drugi+trzeci?

Tak, chodziło mi o najprostszy przypadek, napisałem szybko powyższą 
pętlę, tylko się okazuje że nie uwzględnia przypadków gdy pierwszy 
krótki a drugi długi.

W dniu 18.11.2019 o 15:47, godek.maciek@gmail.com pisze:
> W dniu poniedziałek, 18 listopada 2019 14:09:47 UTC+1 użytkownik Borneq napisał:

>> Mam liczby 1,5,7,10,100,5,6,
> groups [1,5,7,10,100,5,6] (\x -> (sum x) >= 10)
> [[1,5,7],[10],[100],[5,6]]
> 

Ten przykład niezbyt dobry, bo 5 <10 i mój sposób też zadziała,
ale weźmy:
1,10,7,3,10,100,5,6,

W dniu poniedziałek, 18 listopada 2019 19:51:20 UTC+1 użytkownik Borneq napisał:

> 
> >> Mam liczby 1,5,7,10,100,5,6,
> > groups [1,5,7,10,100,5,6] (\x -> (sum x) >= 10)
> > [[1,5,7],[10],[100],[5,6]]
> > 
> 
> Ten przykład niezbyt dobry, bo 5 <10 i mój sposób też zadziała,
> ale weźmy:
> 1,10,7,3,10,100,5,6,

To mi daje coś takiego:

[[1,10],[7,3],[10],[100],[5,6]]

Tutaj sobie możesz potestować:

https://rextester.com/HGC85517

W dniu poniedziałek, 18 listopada 2019 20:08:40 UTC+1 użytkownik godek...@gmail.com napisał:
> W dniu poniedziałek, 18 listopada 2019 19:51:20 UTC+1 użytkownik Borneq napisał:
> 
> > 
> > >> Mam liczby 1,5,7,10,100,5,6,
> > > groups [1,5,7,10,100,5,6] (\x -> (sum x) >= 10)
> > > [[1,5,7],[10],[100],[5,6]]
> > > 
> > 
> > Ten przykład niezbyt dobry, bo 5 <10 i mój sposób też zadziała,
> > ale weźmy:
> > 1,10,7,3,10,100,5,6,
> 
> To mi daje coś takiego:
> 
> [[1,10],[7,3],[10],[100],[5,6]]
> 
> Tutaj sobie możesz potestować:
> 
> https://rextester.com/HGC85517

Trochę poprawiłem nazwy i formatowanie, może teraz będzie nieco czytelniejsze:
https://rextester.com/CRWPJS53169

W dniu 18.11.2019 o 23:40, godek.maciek@gmail.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])

?

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

W dniu 19.11.2019 o 17:11, godek.maciek@gmail.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?

W dniu 19.11.2019 o 17:11, godek.maciek@gmail.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++

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

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