boolean_functions/permutation.cpp at main · jsliyuan/boolean_functions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
/*
Permutation class can implement basic operations, such as left multiplication and right multiplication,
on the generators of some generalized rotation symmetric class.
*/

#include "permutation.h"

#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <iterator>
#include <time.h>
#include <vector>

using namespace std;

Permutation::Permutation(int n) {
  this->n=n;
  this->perm = new int[n];
  for(int i=0; i<n; i++) {
    this->perm[i]=i+1;
  }
  // initialize random seed
  srand(time(NULL));
}

bool Permutation::set(int* perm1) {
  if((int) sizeof(perm)>n-1) {
    cout<<"ERR: too many numbers in set()"<<endl;
  }
  if((int) sizeof(perm)<n-1) {
    cout<<"ERR: too few numbers in set()"<<endl;
  }
  for(int i=0;i<n;i++) {
    this->perm[i]=perm1[i];
  }
  return true;
}

bool Permutation::set(string perm1) {
  stringstream text_stream(perm1);
  string item;
  int num=0;
  while (std::getline(text_stream, item, ',')) {
    this->perm[num]=stoi(item);
    num++;
    if(num>n) {
      cout << "ERR: too many numbers in set()"<<endl;
      return false;
    }
  }
  if(num<n) {
    cout << "ERR: too few numbers in set()"<<endl;
    return false;
  }
  return true;
}

bool Permutation::set(int idx, int val){
  if(idx<1||idx>n) {
    return false;
  }
  if(val<1||val>n) {
    return false;
  }
  this->perm[idx-1]=val;
  return true;
}

std::string Permutation::get_str() const {
  string result ="";
  for (int i = 0; i < n; i ++) {
    if(i<n-1)
      result +=std::to_string(this->perm[i])+ ",";
    else
      result+=std::to_string(this->perm[i]);
  }
  return result;
}

void Permutation::copy_data(const Permutation& perm1) {
  //if(this->perm)
  //  delete this->perm;
  this->n = perm1.var_num();
  this->perm = new int[n];
  memcpy(this->perm, perm1.perm, n*sizeof(int));
}

// Assignment constructor
Permutation& Permutation::operator=(const Permutation& P) {
  if(this->perm){
    delete this->perm;
  }
  copy_data(P);
  return *this;
}

Permutation::Permutation(const Permutation& P){
  copy_data(P);
}

int Permutation::var_num() const {
  return this->n;
}

void Permutation::left_mult(const Permutation& perm1){
  int a;
  int* term;
  term=new int[n];
  for(int i=0;i<n;i++){
    term[i]=this->perm[i];
  }
  for(int j=0;j<n;j++){
      this->perm[j]=term[perm1.perm[j]-1];
  }
}

void Permutation::right_mult(const Permutation& perm1){
  int a;
  int* term;
  term=new int[n];
  for(int i=0;i<n;i++) {
    term[i]=this->perm[i];
  }
  for(int j=0;j<n;j++) {
      this->perm[j]=perm1.perm[term[j]-1];
  }
}

// BooleanFun destructor
Permutation::~Permutation()
{
  delete perm;
}

// Decompose the permutation into cycles.
// Returns the length of each cycle, as a vector.
std::vector<int> Permutation::cycles() const {
  bool visisted[n];
  memset(visisted, 0, n * sizeof(bool));
  vector<int> result;

  for (int i = 0; i < n; i ++) {
    if (visisted[i] == false) {
      int idx = perm[i] - 1;
      int len = 0;
      while (!visisted[idx]) {
        visisted[idx] = true;
        idx = perm[idx] - 1;
        len ++;
      }
      result.push_back(len);
    }
  }
  return result;
}