# gdd

**Repository Path**: public_share/gdd

## Basic Information

- **Project Name**: gdd
- **Description**: 群组决策
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2024-03-14
- **Last Updated**: 2024-03-14

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# Group Decision Diagram

Group Decision Diagram (GDD) is a data structure to maintain a subset of a permutation group.
This is a C++ implementation of GDD.

## Install

This is a header-only library. Please copy the files in ./include

## Usage

````
#include <bits/stdc++.h>
#include "gdd.hh"
#include "permutation.hh"
#include "memoryusage.hh"
#include "util.hh"

using namespace std;

int main() {
  Permutation R = Permutation::parse(24, "(12,13,15,14)(9,1,18,21)(11,3,16,23)");
  Permutation U = Permutation::parse(24, "(0,1,3,2)(8,4,16,12)(9,5,17,13)");
  Permutation F = Permutation::parse(24, "(8,9,11,10)(2,12,21,7)(3,14,20,5)");

  int n = U.n;
  vector<Permutation> gen = {R, U, F};
  
  GroupDecisionDiagram gdd(gen);
  auto order = gdd.groupOrder();
  cout << "Group Order = " << order << endl;

  int z = gdd.top;
  for (Permutation g: gen) {
    z = gdd.cup(z, gdd.singleton(g));
    z = gdd.cup(z, gdd.singleton(g.inv()));
  }

  cout << "i: time | #GDDSize | #TotalGDDSize | Cardinality" << endl;
  auto prev = order; prev = 1;
  int w = gdd.top;

  for (int iter = 1; iter < 15; ++iter) {
    w = gdd.cartesianProduct(z, w);
    cout << iter << ": " << diff << " | ";
    auto count = gdd.cardinality(w);
    cout << gdd.numberOfNodes(w) << " | " << gdd.node.size() << " | " << count << " || " << count - prev << endl;
    if (count == order) break;
    prev = count;
  }
  return 0;
}
````

````
> g++ main.cc
> ./a.out
````

## Performance

### Rubik Cube's puzzle:

|         |        |         |           |            |               |
| :-----: | -----: | ------: | --------: | ---------: | ------------: |
|  \(k\)  |      3 |       4 |         5 |          6 |             7 |
| \#Conf. |  1,068 |  10,011 |    93,840 |    878,880 |     8,221,632 |
| GDD (size) |  6,537 |  58,850 |   476,497 |  3,641,049 |    26,721,270 |
| GDD (time) |  0.02s |   0.30s |     3.54s |     35.04s |        338.2s |
| piDD (size) | 26,166 | 247,770 | 2,319,674 | 21,062,444 |             — |
| piDD (time) |  0.11s |   1.80s |     23.4s |     247.3s | \(\ge\) 7200s |
| rhoDD (size)  | 36,799 | 331,549 | 2,978,733 | 26,715,003 |             — |
| rhoDD (time) |  0.51s |   6.36s |     58.5s |     572.9s | \(\ge\) 7200s |

piDD, rhoDD are existing data structure for the same purpose.

## Reference 

- Takanori Maehara and Yuma Inoue (2019): "Group Decision Diagram (GDD): A Compact Representation for Permutations", in Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI'19), Honolulu, Hawaii, United States, January 27--February 01, 2019.