Skip to content

Instantly share code, notes, and snippets.

View cocomoff's full-sized avatar
🏠
Working from home

Keisuke OTAKI cocomoff

🏠
Working from home
View GitHub Profile
@cocomoff
cocomoff / emp_entropy.py
Created June 16, 2019 14:51
経験エントロピー(おそらく正しくない)
# -*- coding: utf-8 -*-
import re
from math import log2
from itertools import product
from collections import Counter
def powerK(loe, K):
if K < 0:
raise AssertionError("K must be positive")
@cocomoff
cocomoff / simple_BWT.py
Created June 16, 2019 23:28
BWT (figure 3.1)
# -*- coding: utf-8 -*-
if __name__ == '__main__':
T = "abracadabra$"
lT = len(T)
print("Input:", T)
sa = [T[i:] for i in range(lT)]
isa = list(zip(range(lT), sa))
sorted_isa = sorted(isa, key=lambda x: x[1])
@cocomoff
cocomoff / several_coding_examples.py
Created June 19, 2019 11:32
高速文字列解析の世界 §2.5 符号
# -*- coding: utf-8 -*-
def unary(x):
return "0" * (x - 1) + "1"
def binary(x):
return bin(x)[2:]
def gamma(x):
bx = binary(x)
@cocomoff
cocomoff / example_bs.cpp
Created June 30, 2019 08:53
bit vector example
/*
g++ -std=c++14 -o main main.cpp -I/home/cocomoff/sdsl-lite/build/include -L/home/cocomoff/sdsl-lite/build/lib -lsdsl -ldivsufsort -ldivsufsort64
*/
#include <bits/stdc++.h>
#include <sdsl/int_vector.hpp>
#include <sdsl/bit_vectors.hpp>
#include <sdsl/rank_support.hpp>
#include <sdsl/util.hpp>
@cocomoff
cocomoff / example_wt.cpp
Created July 3, 2019 14:07
wavelet tree of integer values
#include <bits/stdc++.h>
#include <sdsl/wavelet_trees.hpp>
using namespace std;
using namespace sdsl;
int main() {
wt_int<rrr_vector<63>> wt;
// auto iv = int_vector<>({0, 7, 2, 1, 4, 3, 6, 7, 2, 5, 0, 4, 7, 2, 6, 3});
auto iv = int_vector<>({0, 2, 1, 3, 2, 0, 2, 3});
@cocomoff
cocomoff / example_bdd_constraint.cpp
Last active July 4, 2019 00:27
example_bdd_constraint.cpp
#include <iostream>
#include <random>
#include <vector>
#include "cuddObj.hh"
using namespace std;
int main() {
Cudd mgr;
@cocomoff
cocomoff / example_bdd_constraint_var18.cpp
Created July 4, 2019 00:39
example_bdd_constraint_var18.cpp
#include <iostream>
#include <random>
#include <vector>
#include "cuddObj.hh"
using namespace std;
int main() {
Cudd mgr;
@cocomoff
cocomoff / multidag_longest_path.py
Created July 4, 2019 01:24
multidag_longest_path.py
# -*- coding: utf-8 -*-
import networkx as nx
import networkx.algorithms as nxa
def longest_path_for_multidigraph(G, weight='weight', default_weight=1):
dist = {}
for v in nx.topological_sort(G):
us = []
for u, data in G.pred[v].items():
@cocomoff
cocomoff / example_tdzdd_01knapsack.cpp
Created July 8, 2019 01:32
example_tdzdd_01knapsack.cpp
#include <fstream>
#include <iostream>
#include <tdzdd/DdSpec.hpp>
#include <tdzdd/DdStructure.hpp>
using namespace std;
class KnapsackZdd : public tdzdd::DdSpec<KnapsackZdd, int, 2> {
int const n;
int const *w;
@cocomoff
cocomoff / example_tdzdd.cpp
Created July 8, 2019 02:22
example_tdzdd.cpp
#include <fstream>
#include <iostream>
#include <tdzdd/DdSpec.hpp>
#include <tdzdd/DdStructure.hpp>
using namespace std;
const bool DEBUG_ENUM = false;
class Combination : public tdzdd::DdSpec<Combination, int, 2> {