Kombinacje/Permutacje

Część,

Próbuję napisać kod, który generowałby wszystkie możliwe kombinacje zbioru, który może mieć od 1 do 10 elementów, a każdy element może mieć wartość od 0 do 4 (oczywiście mowa tylko o liczbach całkowitych).

Np weźmy przypadek, że zbiór jest 2-elementowy jego kombinacje wyglądały by tak:

00
01
10
11
02
20
12
21
22
.
.
.
44

Jestem dość początkujący, przykładowa implementacja bądź jakiś artykuł/poradnik/link/cokolwiek co pozwoliło by mi rozwiązać to zadanie było by bardzo pomocne.

Na początek możesz zagnieździć pętlę for wielokrotnie.

for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 5; j++) {
        System.out.println(String.valueOf(i) + String.valueOf(j));
    }
}

Potem możesz pokombinować z rekurencją.

const tokens = [0, 1, 2, 3, 4];

function generateLevel(n) {

    if (n === 1) {
        return tokens;
    }

    let soFar = generateLevel(n - 1);

    const result = [];

    for (let i = 0; i < tokens.length; i++) {
        for (let j = 0; j < soFar.length; j++) {
            let e = '' + tokens[i] + soFar[j];
            result.push(e);
        }
    }

    return result;
}

Na szybko test

for (let i = 1; i <= 2; i++) {
    generateLevel(i)
        .forEach(e => console.log(e));
}

co zobrazuje twój prosty zestaw obrazujący zadanie

0
1
2
3
4
00
01
02
03
04
10
11
12
13
14
20
21
22
23
24
30
31
32
33
34
40
41
42
43
44

I dla pełnego zakresu 1 do 10 możliwych elementów w zbiorze.

for (let i = 1; i <= 10; i++) {
    generateLevel(i)
        .forEach(e => console.log(e));
}

Razem 5+ 55 + 55*5 + ... + 5^10 (suma szeregu geometrycznego) pozycji do wyświetlenia
(1-5^11)/(1-5) = 12 207 031 (minus 1 bo ty nie masz zbioru pustego)
5(1-5^10)/(1-5) = 12 207 030 (prościej)

https://pl.wikipedia.org/wiki/Szereg_geometryczny

Nie uruchamiaj dla wartości zbliżonych do level = 10 bo się naczekasz na wyświetlenie wszystkich linijek ;)

Nie ma większych ograniczeń, w przykładzie liczby i tak traktowane jak string i sklejane rekurencyjnie w inny dłuższy string.

https://pl.wikipedia.org/wiki/Kombinacja_z_powtórzeniami
https://pl.wikipedia.org/wiki/Kombinacja_bez_powtórzeń
https://pl.wikipedia.org/wiki/Permutacja

Bo coś mi nie pasuje opis do przykładowego wyniku. Napisałem kod generujący oczekiwany przykładowy wynik.

Trochę skomplikowane (dwie funkcje pomocnicze), rozwija algorytm generowania wszystkich binarnych sekwencji o długości n, stąd zmiana bazy (sekwencje binarne to tylko długości 2), tu będzie działać do m = 16, bo max do systemu szesnastkowego konwertuje decToAny, ze względu na indeksowanie, aby dostać do czterech trzeba podać m= 5:

import java.util.*;
import java.math.*;

class Main {
  public static String decToAny(int n, int base) {
      String convString = "0123456789ABCDEF";
      if (n < base) 
        return convString.substring(n, n  + 1);
      else
          return decToAny(n / base, base) + convString.substring(n % base, n % base + 1);
  }

  public static String appendZeroes(String x, int n, int base) {
    x = decToAny(Integer.valueOf(x), base);
    String out = "";
    for (int i = 0; i < n - x.length(); i++)
      out += "0";
    return out + x;
  }

  public static List<String> extendedPowSet(int n, int m) {
    String start = "0";
    int k = 0;
    List<String> out = new ArrayList<>();
    String tmp = "";
    for (int j = 0; j < n; j++)
      tmp += "0";
    out.add(tmp);
    while (k < (int) Math.pow(m, n) - 1) {
      k += 1;
      start = appendZeroes(String.valueOf(k), n, m);
      out.add(start);
    }
    return out;
  }
  public static void main(String[] args) {

    System.out.println(extendedPowSet(2, 5)); // -> to co Chcesz
  }
}

Zrób sobie licznik. Licznik jest tabelą 10-elementową początkowo wypełnioną zerami. W każdym przebiegu pętli inkremujesz ostatni element, jeśli masz przepełnienie, zerujesz i przenosisz w lewo jedność i robisz test przepełnienia w komórce zawierającą kolejny rząd wielkości. Program kończy pracę, gdy wszystkie komórki wypełnione są czwórkami. Początkowe zera wiodące uznajesz za pustkę, zatem 0000000040 jest zbiorem zawierającym tylko dwa elementy.

Można by to zrobić w jeszcze jeden sposób:

• robisz pętlę od 0 do 4^10 (1048576),
• zamieniasz każdą cyfrę 10-wą w dwie cyfry 5-tkowe wg. wzorca:
  0 - 00
  1 - 01
  2 - 02
  3 - 03
  4 - 04
  5 - 10
  6 - 11
  7 - 12
  8 - 13
  9 - 14

#include <iostream>
#include <vector>
#include <string>
using namespace std;

typedef void showproc(const string &result);
typedef showproc *showptr;

void show(const string &result)
{
    cout<<result<<endl;
}

string prepare(const vector<int> &idx,const string &alphas)
{
    string str(idx.size(),'\0');
    for(size_t i=0;i<idx.size();++i) str[i]=alphas[idx[i]];
    return str;
}

bool next(vector<int> &idx,size_t maxvalue)
{
    for(size_t i=idx.size()-1;i<idx.size();idx[i--]=0) if(++idx[i]<maxvalue) return true;
    return false;
}

void permutations(size_t size,const string &alphas,showptr show)
{
    vector<int> idx(size,0);
    do { show(prepare(idx,alphas)); } while(next(idx,alphas.size()));
}

void permutations(size_t minsize,size_t maxsize,string alphas,showptr show)
{
    for(size_t size=minsize;size<=maxsize;++size) permutations(size,alphas,show);
}

int main()
{
    permutations(2,4,"ABCD",&show);    
}

https://ideone.com/92Doin

import java.io.*;

public class Main
{
   public static void main(String[] args)
   {
      Permutation.make(2,4,"ABCD".toCharArray(),(str) -> System.out.println(str) );
   }
}

class Permutation
{
   public interface YeldString { void Yeld(String str); }
   private static boolean next(int[] idx,int maxvalue)
   {
      for(int i=idx.length-1;i>=0;idx[i--]=0) if(++idx[i]<maxvalue) return true;
      return false;
   }
   private static String prepare(int[] idx,char[] alphas)
   {
      char[] str=new char[idx.length];
      for(int i=0;i<idx.length;++i) str[i]=alphas[idx[i]];
      return new String(str);
   }
   public static void make(int size,char[] alphas,YeldString yeld)
   {
      int[] idx=new int[size];
      do { yeld.Yeld(prepare(idx,alphas)); } while(next(idx,alphas.length));
   }
   public static void make(int minsize,int maxsize,char[] alphas,YeldString yeld)
   {
      for(int size=minsize;size<=maxsize;++size) make(size,alphas,yeld);
   }
}

https://ideone.com/lmMyz1