fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdint>
  4. #include <random>
  5. #include <algorithm>
  6. #include <map>
  7. #include <chrono>
  8. #include <limits>
  9. #include <stdexcept>
  10. //copyright@yakitori2014 AllRightsReserved
  11. //i dont lisence for any one.
  12. //if need to find me and ask me.
  13.  
  14. typedef std::vector<std::uint8_t> btype;
  15. typedef std::vector<std::pair<std::uint8_t,uint64_t>> rltype;
  16.  
  17. btype MakeData(std::size_t N = 1024){
  18.  
  19. 	std::random_device RD;
  20. 	//std::mt19937 mt(RD());
  21. 	std::mt19937 mt(0);
  22. 	std::uniform_int_distribution<int> uid(0, 255);
  23.  
  24. 	btype data;
  25.  
  26. 	for (std::size_t i = 0; i < N; i++){
  27. 		data.push_back(uid(mt));
  28. 	}
  29. 	return data;
  30. }
  31.  
  32. std::pair<std::uint64_t,btype> PermSort(btype& B,bool IsShow=false){
  33. 	btype T = B;
  34. 	std::uint64_t i=0;
  35. 	bool F = false;
  36.  
  37. 	while (std::is_sorted(T.begin(), T.end())==false){
  38. 		if (std::next_permutation(T.begin(), T.end()) == false){
  39. 			if (F == true){
  40. 				std::cout << "パーミテーションに失敗" << std::endl;
  41. 				throw std::logic_error("パーテーションに失敗！！");
  42. 			}
  43. 			F = true;
  44. 		}
  45. 		i++;
  46. 		if(IsShow==true) std::cout << i << '/' << std::numeric_limits<std::uint64_t>::max() << '\r';
  47. 	}
  48. 	if(IsShow==true) std::cout << std::endl;
  49.  
  50. 	return std::make_pair(i,T);
  51. }
  52.  
  53. btype PermDeSort(btype RLD, std::uint64_t N){
  54. 	auto R = RLD;
  55. 	for (std::uint64_t i = 0; i < N; i++){
  56. 		std::prev_permutation(R.begin(), R.end());
  57. 	}
  58. 	return R;
  59. }
  60.  
  61. rltype RunLengthComp(btype& B){
  62. 	std::uint8_t Number = B.front();
  63. 	std::uint64_t C = 0;
  64. 	rltype ret;
  65.  
  66. 	for (std::size_t i = 0; i < B.size(); i++){
  67. 		if (Number == B[i]){
  68. 			C++;
  69. 		}
  70. 		else{
  71. 			ret.push_back(std::make_pair(Number, C));
  72. 			Number = B[i];
  73. 			i--;
  74. 			C = 0;
  75.  
  76. 		}
  77. 	}
  78. 	ret.push_back(std::make_pair(Number, C));
  79.  
  80. 	return ret;
  81. }
  82.  
  83. btype RunLengthExt(rltype rl){
  84. 	std::uint8_t Number = rl.front().first;
  85. 	std::uint64_t C = rl.front().second;
  86. 	btype ret;
  87. 	for (std::size_t i = 0; i < rl.size(); i++){
  88. 		Number = rl[i].first;
  89. 		C = rl[i].second;
  90. 		for (std::uint64_t N = 0; N < C; N++){
  91. 			ret.push_back(Number);
  92. 		}
  93. 	}
  94. 	return ret;
  95. }
  96.  
  97.  
  98. std::pair<std::uint64_t, rltype> Encode(btype& B, bool IsCheck = false){
  99.  
  100.  
  101. 	auto A = PermSort(B);
  102. 	if (IsCheck == true){
  103. 		auto T = B;
  104. 		std::sort(T.begin(), T.end());
  105. 		if (A.second == T)std::cout << "ソート完了" << std::endl;
  106. 		else std::cout << "ソート失敗" << std::endl;
  107. 	}
  108. 	auto RL = RunLengthComp(A.second);
  109.  
  110. 	return std::make_pair(A.first, RL);
  111. }
  112.  
  113. btype Decode(std::pair<std::uint64_t, rltype> D){
  114. 	auto A = RunLengthExt(D.second);
  115. 	auto B = PermDeSort(A, D.first);
  116.  
  117. 	return B;
  118. }
  119. int main(){
  120.  
  121. 	auto Start = std::chrono::high_resolution_clock::now();
  122.  
  123. 	auto D = MakeData(11);//ここを16にしてみよう。オーダーはo(N!)だ！！！！！
  124. 	auto B = D;
  125.  
  126. 	std::cout <<"オリジナル:"<< std::endl;
  127. 	for (auto& o : D) std::cout << static_cast<int>(o) << ',';
  128. 	std::cout << std::endl;
  129.  
  130.  
  131.  
  132. 	auto En = Encode(D, true);
  133. 	auto De = Decode(En);
  134.  
  135.  
  136. 	std::cout <<"デコード:"<< std::endl;
  137. 	for (auto& o : De) std::cout << static_cast<int>(o) << ',';
  138. 	std::cout << std::endl;
  139. 	for (auto& o : En.second)std::cout << static_cast<int>(o.first) << ':' << o.second << ',';
  140. 	std::cout << std::endl;
  141. 	std::cout <<"エンコード:"<< std::endl;
  142.  
  143. 	auto End = std::chrono::high_resolution_clock::now();
  144.  
  145.  
  146. 	auto E = std::chrono::duration_cast<std::chrono::milliseconds>(End - Start);
  147.  
  148. 	std::cout << "経過時間は" << E.count() << "msだ！"<<std::endl;
  149. 	std::cout << "ソート回数は" << En.first << "回だ！" << std::endl;
  150.  
  151. 	return 0;
  152. }
Success #stdin #stdout 0.48s 3440KB
comments (?)
stdin 
Standard input is empty
stdout 
オリジナル:
140,151,183,216,154,219,139,216,108,159,165,
ソート完了
デコード:
140,151,183,216,154,219,139,216,108,159,165,
108:1,139:1,140:1,151:1,154:1,159:1,165:1,183:1,216:2,219:1,
エンコード:
経過時間は489msだ！
ソート回数は15851238回だ！
https://ideone.com/stwHzp
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!