길이가 같은 두 줄 사이 의 해밍 거리는 해당 기호가 다른 위치 수입니다.
하자 P길이의 이진 문자열 n과 T길이의 이진 문자열 2n-1. 왼쪽에서 오른쪽으로 순서대로 모든 길이의 하위 문자열 n사이 의 해밍 거리를 계산하여 배열 (또는 목록)에 넣을 수 있습니다.PnT
해밍 거리 시퀀스 예
하자 P = 101및 T = 01100. 이 쌍에서 얻는 해밍 거리의 순서는 2,2,1입니다.
친밀감의 정의
이제 그러한 두 개의 해밍 거리 시퀀스를 고려해 봅시다. 말 x = (0, 2, 2, 3, 0)과 y = (2, 1, 4, 4, 2)사례 등. 우리는 그런 말을 x하고 y있는 close경우 y <= x <= 2*y또는 경우 x <= y <= 2*x. 여기서 스칼라 곱셈과 부등식은 요소별로 취해집니다. 즉 두 시퀀스를 들어, 말을 A하고 B, A <= B iff A[i] <= B[i]모든 인덱스에 대해 i.
해밍 거리의 시퀀스는 이를 비교하는 이러한 방식으로 부분적인 순서를 형성한다는 점에 유의하십시오 . 다시 말해서, 많은 쌍의 서열은 서로 크거나 같거나 작지 않다. 예를 들어 (1,2)및 (2,1).
따라서 위의 예를 사용 (0, 2, 2, 3, 0) <= 2*(2, 1, 4, 4, 2) = (4, 2, 8, 8, 4)하지만 (0, 2, 2, 3, 0)보다 크지 않습니다 (2, 1, 4, 4, 2). 또한 (2, 1, 4, 4, 2)보다 작거나 같습니다 2*(0, 2, 2, 3, 0) = (0, 4, 4, 6, 0). 결과 x와 y하지 서로 가까이 있습니다.
직무
증가 n에서 시작 n=1, 이진 문자열의 모든 가능한 쌍을 고려 P길이 n및 T길이를 2n-1. 있다 2^(n+2n-1)이러한 쌍 따라서 해밍 거리의 많은 시퀀스. 그러나 이러한 많은 시퀀스는 동일합니다. 과제는 두 시퀀스가 서로 가까이 있지 않도록 가장 큰 해밍 거리 시퀀스 세트의 크기를 찾는 것입니다.
코드는의 값당 하나의 숫자를 출력해야합니다 n.
점수
귀하의 점수는 n5 분 안에 내 컴퓨터에서 코드가 도달 하는 최고 점수입니다 (그러나 읽기). 타이밍은 총 실행 시간이 아닌 시간입니다 n.
최적이 아닌 답변에 대한 점수를 제공하려면 최적의 답변을 찾기가 어려울 수 있으므로 약간 미묘한 점수 시스템이 필요합니다. 귀하의 점수는 n이보다 작은 모든 크기에 대해 다른 사람이 더 높은 정답을 게시하지 않은 최고 값입니다 . 예를 들어, 당신이 출력 2, 4, 21하고 다른 사람이 출력 2, 5, 15하면 1다른 사람이에 대한 더 나은 답변을 얻을 때만 점수 를 매 깁니다 n = 2. 당신이 출력 2, 5, 21하면 3그 답변이 모두 최적이기 때문에 다른 사람이 무엇을 출력하든 점수를 매길 것 입니다. 당신은 모든 최적의 답변을 가지고 있다면 분명히 당신은 n당신이 게시 한 최고 점수를 얻을 것이다 . 그러나 귀하의 답변이 최적이 아니더라도 다른 사람이 이길 수 없다면 여전히 점수를 얻을 수 있습니다.
답변 예 및 작동 예
(이 답변은 아직 확인되지 않은 상태입니다. 독립적 인 확인을 받으면 감사하겠습니다.)
ETHproduction 덕분에 :
- n = 1은 2입니다.
- n = 2는 5입니다.
- n = 3은 21을 제공합니다.
좀 n = 2더 자세히 살펴 보자 . 이 경우 해밍 거리 시퀀스의 전체 목록 (여기서는 튜플로 표시)은 다음과 같습니다.
[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]
우리는 그것이 (0,0)다른 튜플에 가깝지 않다는 것을 알 수 있습니다 . 우리가 가지고가는 경우 사실 (0, 0), (0, 1), (1, 0), (2, 1), (1,2)그 튜플 사항도 가까이 다른 사람의에 없습니다. 이 점수 부여 5를 들어 n = 2.
들어 n = 3별개의 해밍 거리 시퀀스의 전체 목록은 다음과 같습니다
[(0, 0, 0), (0, 0, 1), (0, 1, 1), (0, 1, 2), (0, 1, 3), (0, 2, 1), (0, 2, 2), (0, 2, 3), (0, 3, 0), (0, 3, 1), (1, 0, 0), (1, 0, 1), (1, 0, 2), (1, 1, 0), (1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 2, 0), (1, 2, 1), (1, 2, 2), (1, 2, 3), (1, 3, 0), (1, 3, 1), (1, 3, 2), (2, 0, 1), (2, 0, 2), (2, 0, 3), (2, 1, 0), (2, 1, 1), (2, 1, 2), (2, 1, 3), (2, 2, 0), (2, 2, 1), (2, 2, 2), (2, 2, 3), (2, 3, 1), (2, 3, 2), (2, 3, 3), (3, 0, 2), (3, 0, 3), (3, 1, 0), (3, 1, 1), (3, 1, 2), (3, 2, 0), (3, 2, 1), (3, 2, 2), (3, 3, 2), (3, 3, 3)]
이 48시퀀스 중에서 크기 세트를 선택하여 해당 세트의 21쌍이 서로 가까이 있지 않도록 할 수 있습니다 .
언어와 라이브러리
원하는 언어와 라이브러리를 사용할 수 있습니다. 가능한 경우 코드를 실행할 수 있으면 좋을 것이므로 가능한 경우 Linux에서 코드를 실행 / 컴파일하는 방법에 대한 자세한 설명을 포함하십시오.
내 컴퓨터 타이밍이 64 비트 컴퓨터에서 실행됩니다. 이것은 8GB RAM, AMD FX-8350 8 코어 프로세서 및 Radeon HD 4250이 포함 된 표준 우분투 설치입니다. 또한 코드를 실행할 수 있어야합니다.
최고의 답변
- Christian Sievers의 2, 5, 21, 83, 361 점은 4 점 입니다. C ++
- 점수의 5 가 2, 5, 21, 83 fənɛtɪk 372. 자바 스크립트
답변
igraph 라이브러리를 사용하는 C ++
새로운 도서관을 배울 수있는 좋은 기회를 주셔서 감사합니다!
이 프로그램은 이제 2, 5, 21, 83, 361빨리 계산 합니다. PRINTNODES상수 를 사용하여 노드 인쇄를 제어 할 수 있습니다 .
사용 된 그래프에는 거리 벡터에 해당하는 노드 사이에 여분의 가장자리가 있습니다. 여기서 거리 벡터는 다른 하나와 거꾸로되어 있습니다. 계산 속도가 빨라지고 발견 된 독립 세트는 물론 원래 그래프 중 하나입니다. 또한 완전히 적용되지 않더라도 계산 된 독립 세트는 복귀시 닫힙니다. 나는 그 속성을 가진 최대 독립 세트가 항상 존재한다고 생각합니다. 에 대해 하나 이상이 n<=4있습니다. (83이 최적임을 보여줄 수 있다고 확신합니다.)
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#include<igraph.h>
using vect = std::vector<int>;
constexpr int MAXDIRECT=100;
constexpr int PRINTNODES=1;
std::set<int> avoid{};
igraph_t graph;
std::vector<vect> distance_vectors{};
int count;
int close_h(const vect &a, const vect &b ){
// check one direction of the closeness condition
for(auto i=a.begin(), j=b.begin(); i!=a.end(); i++,j++)
if ( (*i > *j) || (*j > 2 * *i))
return 0;
return 1;
}
int close(const vect &a, const vect &b ){
return close_h(a,b) || close_h(b,a);
}
vect distances(int n, int p, int t){
vect res{};
for (int i=0; i<n; ++i){
int count = 0;
for (int j=0; j<n; ++j)
count += 1 & ((p>>j)^(t>>j));
res.push_back(count);
t >>= 1;
}
return res;
}
void print_vect( vect &v ){
std::cout << "(";
auto i=v.begin();
std::cout << *i++;
for( ; i!=v.end(); ++i)
std::cout << "," << *i ;
std::cout << ")\n";
}
void use_node( int n ){
if(PRINTNODES)
print_vect( distance_vectors[n] );
++count;
avoid.insert( n );
igraph_vector_t neighs;
igraph_vector_init( &neighs, 0 );
igraph_neighbors( &graph , &neighs, n, IGRAPH_OUT );
for(int i=0; i<igraph_vector_size( &neighs ); ++i)
avoid.insert( VECTOR(neighs)[i] );
igraph_vector_destroy( &neighs );
}
void construct(int n){
std::set<vect> dist_vects;
for(int p=0; p>>n == 0; ++p)
for(int t=0; t>>(2*n-2) == 0; ++t) // sic! (because 0/1-symmetry)
dist_vects.insert(distances(n,p,t));
int nodes = dist_vects.size();
std::cout << "distinct distance vectors: " << nodes << "\n";
distance_vectors.clear();
distance_vectors.reserve(nodes);
std::copy(dist_vects.begin(), dist_vects.end(),
back_inserter(distance_vectors));
igraph_vector_t edges;
igraph_vector_init( &edges, 0 );
igraph_vector_t reversed;
igraph_vector_init_seq( &reversed, 0, nodes-1 );
for (int i=0; i<nodes-1; ++i){
vect &x = distance_vectors[i];
vect xr ( x.rbegin(), x.rend() );
for(int j=i+1; j<nodes; ++j){
vect &y = distance_vectors[j];
if( xr==y ){
VECTOR(reversed)[i] = j;
VECTOR(reversed)[j] = i;
}else if( close( x, y ) || close( xr, y) ){
igraph_vector_push_back(&edges,i);
igraph_vector_push_back(&edges,j);
}
}
}
std::cout << "edges: " << igraph_vector_size(&edges)/2 << "\n";
igraph_create( &graph, &edges, nodes, IGRAPH_UNDIRECTED);
igraph_vector_destroy( &edges );
igraph_cattribute_VAN_setv( &graph, "r", &reversed );
igraph_vector_destroy( &reversed );
igraph_vector_t names;
igraph_vector_init_seq( &names, 0, nodes-1 );
igraph_cattribute_VAN_setv( &graph, "n", &names );
igraph_vector_destroy( &names );
}
void max_independent( igraph_t *g ){
igraph_vector_ptr_t livs;
igraph_vector_ptr_init( &livs , 0 );
igraph_largest_independent_vertex_sets( g, &livs );
igraph_vector_t *nodes = (igraph_vector_t *) VECTOR(livs)[0];
igraph_vector_t names;
igraph_vector_init( &names, 0 );
igraph_cattribute_VANV( g, "n", igraph_vss_vector( nodes ), &names );
for(int i=0; i<igraph_vector_size(&names); ++i)
use_node( VECTOR(names)[i] );
igraph_vector_destroy( &names );
igraph_vector_ptr_destroy_all( &livs );
}
void independent_comp( igraph_t *g );
void independent( igraph_t *g ){
if(igraph_vcount( g ) < MAXDIRECT){
max_independent( g );
return;
}
igraph_vector_ptr_t components;
igraph_vector_ptr_init( &components, 0 );
igraph_decompose( g, &components, IGRAPH_WEAK, -1, 1);
for(int i=0; i<igraph_vector_ptr_size( &components ); ++i)
independent_comp( (igraph_t *) VECTOR(components)[i] );
igraph_decompose_destroy( &components );
}
void independent_comp( igraph_t *g ){
if (igraph_vcount( g ) < MAXDIRECT){
max_independent( g );
return;
}
igraph_vector_t degs;
igraph_vector_init( °s, 0 );
igraph_degree( g, °s, igraph_vss_all(), IGRAPH_OUT, 1 );
int maxpos = igraph_vector_which_max( °s );
igraph_vector_destroy( °s );
int name = igraph_cattribute_VAN( g, "n", maxpos );
int revname = igraph_cattribute_VAN( g, "r", maxpos );
int rev = -1;
if(name!=revname){
igraph_vector_ptr_t reversed_candidates_singleton;
igraph_vector_ptr_init( &reversed_candidates_singleton, 0 );
igraph_neighborhood( g, &reversed_candidates_singleton,
igraph_vss_1(maxpos), 2, IGRAPH_OUT );
igraph_vector_t * reversed_candidates =
(igraph_vector_t *) VECTOR(reversed_candidates_singleton)[0];
igraph_vector_t names;
igraph_vector_init( &names, 0 );
igraph_cattribute_VANV( g, "n", igraph_vss_vector( reversed_candidates ),
&names );
long int pos;
igraph_vector_search( &names, 0, revname, &pos );
rev = VECTOR(*reversed_candidates)[pos];
igraph_vector_destroy( &names );
igraph_vector_ptr_destroy( &reversed_candidates_singleton );
}
igraph_vs_t delnodes;
igraph_vs_vector_small( &delnodes, maxpos, rev, -1 );
igraph_delete_vertices( g, delnodes );
igraph_vs_destroy( &delnodes );
independent( g );
}
void handle(int n){
std::cout << "n=" << n << "\n";
avoid.clear();
count = 0;
construct( n );
independent( &graph );
// try all nodes again:
for(int node=0; node<igraph_vcount( &graph ); ++node)
if(avoid.count(node)==0)
use_node(node);
std::cout << "result: " << count << "\n\n";
igraph_destroy( &graph );
}
int main(){
igraph_i_set_attribute_table( &igraph_cattribute_table );
for(int i=1; i<6; ++i)
handle(i);
}
데비안에서 컴파일하려면 설치 libigraph0-dev하고 수행하십시오
g++ -std=c++11 -Wall -O3 -I/usr/include/igraph -o ig ig.cpp -ligraph.
이전 설명 :
igraph 라이브러리에는 독립 정점 그래프 세트의 최대 크기를 계산하는 기능이 있습니다. 이 문제 n=3는 1 초 이내에 처리 할 수
있으며 일 동안 종료되지 않습니다 n=4.
그래서 내가하는 일은 그래프를 연결된 구성 요소로 분해하고 라이브러리가 작은 ( MAXDIRECT노드 보다 작은 ) 구성 요소를 처리하도록하는 것 입니다. 다른 구성 요소의 경우 정점을 선택하여 삭제합니다. 가장 좋은 경우 그래프를 여러 구성 요소로 나누지 만 일반적으로 그렇지 않습니다. 어쨌든 구성 요소 (하나만있을 수 있음)는 더 작으며 재귀를 사용할 수 있습니다.
분명히 정점의 선택이 중요합니다. 나는 최대 학위 중 하나를 취합니다. n=4역 노드 목록을 사용 하면 더 나은 결과를 얻을 수 있습니다 (그러나 만 ). 그것은 construct기능 의 마술 부분을 설명합니다
.
선택을 개선하는 동안 가치가있을 수 있습니다. 그러나 삭제 된 노드를 재고하는 것이 더 중요해 보입니다. 지금은 다시는 보지 않습니다. 그들 중 일부는 선택된 노드 중 하나와 연결되지 않을 수 있습니다. 문제는 어떤 노드가 독립 세트를 형성하는지 모른다는 것입니다. 하나, 노드를 삭제하면 나머지 노드의 번호가 다시 매겨집니다. 속성을 부착하여 처리 할 수 있습니다. 그러나 더 나쁜 것은 독립 숫자의 계산이이 숫자를 제공하는 것입니다. 라이브러리가 제공하는 가장 좋은 대안은 모든 가장 큰 독립 세트 를 계산 하는 것입니다. 이는 느립니다 (그래프 크기에 얼마나 의존 하는가). 그럼에도 불구하고 이것은 곧바로 갈 것 같습니다. 더 모호하게도 그래프를 정의하는 특별한 방법을 사용할 수 있는지 고려하는 것이 유용 할 것이라고 생각합니다.
n=6나머지 구성 요소에 대한 대기열을 사용하여 재귀를 루프로 교체하면 사례에 도달 할 수 있습니다 (5 분이 아니더라도).
그래프의 구성 요소를 보는 것이 흥미로 웠습니다. 의 경우 n=4, 그 크기입니다
168, 2*29, 2*28, 3, 4*2, 4*1. 가장 큰 것만 직접 처리 할 수 없습니다.
의 경우 n=5, 크기입니다
1376, 2*128, 2*120, 119, several <=6.
그 두 배 크기가 동형 그래프에 해당 할 것으로 예상하지만 항상 하나의 지배적 인 가장 큰 구성 요소가 하나 있기 때문에 이것을 사용하는 것은 가치가없는 것처럼 보입니다.
의 경우 n=6가장 큰 구성 요소에는 11941총계에서 노드 가 포함 15425되며 다음 두 개의 가장 큰 구성 요소는 size 596입니다.
의 n=7경우이 숫자는 107593 (125232), 2647입니다.
답변
자바 스크립트, 서열 : 2,5,21, 81 83,372 67,349
검색을 시작할 때 요소를 임의로 제거하여 4의 값을 높이도록 관리했습니다. 이상하게도 연결이 6 개 이상인 요소 20 개를 제거하면 연결이 8 개 이상인 5 개 요소를 제거하는 것보다 빠릅니다.
이 순서는 아마도 5에 최적이 아니며 4에 최적이 아닐 수도 있습니다.
암호:
input=4;
maxConnections=6;
numRand=20;
hammings=[];
h=(x,y)=>{retVal=0;while(x||y){if(x%2!=y%2)retVal++;x>>=1;y>>=1}return retVal};
for(i=1<<(input-1);i<1<<input;i++){
for(j=0;j<1<<(2*input);j++){
hamming=[];
for(k=0;k<input;k++){
hamming.push(h((j>>k)%(1<<input),i));
}
equal=0;
for(k=0;k<hammings.length;k++){
if(hamming.join("")==hammings[k].join("")){
equal=1;
break;
}
}
if(!equal)hammings.push(hamming);
}
}
adjMat=[];
for(i=0;i<Math.pow(input+1,input);i++){
row=[];
for(j=0;j<Math.pow(input+1,input);j++){
row.push(0);
}
adjMat.push(row);
}
nodes=[]
for(i=0;i<Math.pow(input+1,input);i++){
nodes[i]=0;
}
for(i=0;i<hammings.length;i++){
sum=0;
chkNodes=[[]];
for(j=0;j<input;j++){
chkVal=[];
t=Math.pow(input+1,j);
sum+=t*hammings[i][j];
tmp=[];
for(r=0;r<chkNodes.length;r++){
for(k=hammings[i][j];k<=Math.min(hammings[i][j]*2,input);k++){
stor=[]
for(s=0;s<chkNodes[r].length;s++){
stor.push(chkNodes[r][s])
}
stor.push(k)
tmp.push(stor);
}
}
chkNodes=[];
for(r=0;r<tmp.length;r++){
chkNodes.push(tmp[r])
}
}
nodes[sum]=1;
for(j=0;j<chkNodes.length;j++){
adjSum=0
for(k=0;k<input;k++){
adjSum+=Math.pow(input+1,k)*chkNodes[j][k]
}
if(adjSum!=sum)adjMat[sum][adjSum]=adjMat[adjSum][sum]=1
}
}
t=nodes.length;
for(i=0;i<t;i++){
if(!nodes[i]){
for(k=0;k<t;k++){
adjMat[i][k]=adjMat[k][i]=0
}
}
}
sum=(a,b)=>a+b;
console.log(nodes.reduce(sum))
connections=x=>x.reduce(sum)
counts=adjMat.map(connections);
stor=[];
for(i=0;i<t;i++){
stor.push(nodes[i]);
}
maxRemainder=0;
greater=[]
for(i=0;i<t;i++){
if(nodes[i]&&counts[i]>maxConnections){
greater.push(i);
}
}
if(input==4){
for(w=0;w<greater.length*numRand;w++){
for(i=0;i<t;i++){
nodes[i]=stor[i];
}
counts=adjMat.map(connections);
toRemove=Math.floor(Math.random()*numRand*2)
for(i=0;i<toRemove&&i<greater.length;i++){
rand=Math.floor(Math.random()*greater.length);
if(nodes[greater[rand]]){
nodes[greater[rand]]=0;
for(j=0;j<t;j++){
if(adjMat[rand][j]){
counts[j]--;
}
}
}
}
for(i=0;i<t*t;i++){
max=0;
maxLoc=0;
for(j=0;j<t;j++){
if(counts[j]>=max&&nodes[j]){
max=counts[j];
maxLoc=j;
}
}
if(max>0){
for(j=0;j<t;j++){
if(adjMat[maxLoc][j]){
counts[j]--;
if(counts[j]<max-1&&stor[j]&&!nodes[j]){
nodes[j]=1;
for(k=0;k<t;k++){
if(adjMat[j][k])counts[k]++;
}
}
}
nodes[maxLoc]=0;
}
}
else{
break;
}
}
maxRemainder=Math.max(maxRemainder,nodes.reduce(sum))
//console.log(nodes.reduce(sum));
}
console.log(maxRemainder);
}
else{
for(i=0;i<t*t;i++){
max=0;
maxLoc=0;
for(j=0;j<t;j++){
if(counts[j]>=max&&nodes[j]){
max=counts[j];
maxLoc=j;
}
}
if(max>0){
for(j=0;j<t;j++){
if(adjMat[maxLoc][j]){
counts[j]--;
if(counts[j]<max-1&&stor[j]&&!nodes[j]){
nodes[j]=1;
for(k=0;k<t;k++){
if(adjMat[j][k])counts[k]++;
}
}
}
nodes[maxLoc]=0;
}
}
else{
break;
}
}
console.log(nodes.reduce(sum));
}
프로그램 끝에 추가되어 각각의 선택된 해밍 거리 시퀀스를 보여주는 해밍 거리 시퀀스를 보여줄 수있는 스 니펫
for(i=0;i<t;i++){
if(nodes[i]){
tmp=[]
for(j=0;j<input;j++){
tmp.unshift(Math.floor(i/Math.pow(input+1,j))%(input+1))
}
console.log(tmp.join(""))
output=""
for(j=0;j<t;j++){
if(adjMat[i][j]&&stor[j]){
outArr=[]
for(k=0;k<input;k++){
outArr.unshift(Math.floor(j/Math.pow(input+1,k))%(input+1))
}
output+=" "+outArr.join("");
}
}
console.log(output)
}
}
설명:
먼저 코드는 하위 문자열에서 고유 한 해밍 거리를 모두 생성합니다.
input=3;
hammings=[];
h=(x,y)=>{retVal=0;while(x||y){if(x%2!=y%2)retVal++;x>>=1;y>>=1}return retVal};
for(i=1<<(input-1);i<1<<input;i++){
for(j=0;j<1<<(2*input);j++){
hamming=[];
for(k=0;k<input;k++){
hamming.push(h((j>>k)%(1<<input),i));
}
equal=0;
for(k=0;k<hammings.length;k++){
if(hamming.join("")==hammings[k].join("")){
equal=1;
break;
}
}
if(!equal)hammings.push(hamming);
}
}
다음으로 코드는이 목록을 무 방향 그래프로 변환합니다.
adjMat=[];
for(i=0;i<Math.pow(input+1,input);i++){
row=[];
for(j=0;j<Math.pow(input+1,input);j++){
row.push(0);
}
adjMat.push(row);
}
nodes=[]
for(i=0;i<Math.pow(input+1,input);i++){
nodes[i]=0;
}
for(i=0;i<hammings.length;i++){
sum=0;
chkNodes=[[]];
for(j=0;j<input;j++){
chkVal=[];
t=Math.pow(input+1,j);
sum+=t*hammings[i][j];
tmp=[];
for(r=0;r<chkNodes.length;r++){
for(k=hammings[i][j];k<=Math.min(hammings[i][j]*2,input);k++){
stor=[]
for(s=0;s<chkNodes[r].length;s++){
stor.push(chkNodes[r][s])
}
stor.push(k)
tmp.push(stor);
}
}
chkNodes=[];
for(r=0;r<tmp.length;r++){
chkNodes.push(tmp[r])
}
}
nodes[sum]=1;
for(j=0;j<chkNodes.length;j++){
adjSum=0
for(k=0;k<input;k++){
adjSum+=Math.pow(input+1,k)*chkNodes[j][k]
}
if(adjSum!=sum)adjMat[sum][adjSum]=adjMat[adjSum][sum]=1
}
}
마지막으로 코드는이 그래프를 순환하여 현재 최대 값보다 연결이 적은 노드를 복원하기 전에 각주기마다 연결이 가장 많은 정점을 제거합니다. 이주기를 마치면 남아있는 노드 수를 출력합니다.
t=nodes.length;
for(i=0;i<t;i++){
if(!nodes[i]){
for(k=0;k<t;k++){
adjMat[i][k]=adjMat[k][i]=0
}
}
}
sum=(a,b)=>a+b;
counts=adjMat.map(x=>x.reduce(sum));
stor=[];
for(i=0;i<t;i++){
stor.push(nodes[i]);
}
for(i=0;i<t*t;i++){
max=0;
maxLoc=0;
for(j=0;j<t;j++){
if(counts[j]>=max&&nodes[j]){
max=counts[j];
maxLoc=j;
}
}
if(max>0){
for(j=0;j<t;j++){
if(adjMat[maxLoc][j]){
counts[j]--;
if(counts[j]<max-1&&stor[j]&&!nodes[j]){
nodes[j]=1;
for(k=0;k<t;k++){
if(adjMat[j][k])counts[k]++;
}
}
}
nodes[maxLoc]=0;
}
}
else{
break;
}
}
console.log(nodes.reduce(sum));
세트 :
1:
0 1
2 :
00 01 10 12 21
삼:
000 001 011 013 030 031 100 101 110 111 123 130 132 203 213 231 302 310 312
321 333
4 :
0000 0001 0011 0111 0124 0133 0223 0230 0232 0241 0313 0320 0322 0331 0403
0412 1000 1001 1013 1021 1100 1102 1110 1111 1134 1201 1224 1233 1243 1304
1314 1323 1330 1332 1342 1403 1413 1420 1422 2011 2033 2124 2133 2140 2142
2214 2230 2241 2303 2313 2320 2331 2411 3023 3032 3040 3041 3101 3114 3123
3130 3132 3141 3203 3213 3220 3231 3302 3310 3312 3321 3334 3343 3433 4031
4113 4122 4131 4210 4212 4221 4311 4333
5 :
00000 00001 00011 00111 00123 01112 01235 01244 01324 01343 02111 02230
02234 02333 02342 02432 02441 02522 02530 02531 03134 03142 03220 03224
03233 03241 03314 03323 03331 03403 03412 03421 03520 04133 04141 04214
04223 04232 04303 04313 04322 05042 05050 05051 05132 10000 10001 10011
10122 10212 10221 10245 11000 11001 11013 11022 11100 11112 11120 11121
11202 11211 11345 11353 11443 12012 12111 12201 12245 12253 12335 12344
12352 12425 12430 12434 12442 12513 12532 13033 13042 13244 13252 13325
13330 13334 13342 13404 13424 13433 13441 13520 13522 13531 14032 14051
14140 14152 14225 14230 14234 14241 14243 14304 14315 14324 14332 14413
14420 14422 14431 15041 15050 15125 15133 15142 15215 15223 15232 20112
20135 20211 20253 20334 20352 21012 21021 21102 21110 21111 21201 21245
21344 21352 21430 21433 21442 21514 21523 22011 22101 22135 22244 22252
22325 22334 22340 22343 22405 22415 22424 22441 22520 22522 22531 23041
23144 23150 23152 23225 23234 23240 23243 23251 23304 23315 23324 23333
23341 23403 23413 23420 23432 23521 24031 24050 24125 24130 24134 24142
24151 24215 24224 24233 24303 24314 24320 24323 24331 24412 24421 25123
25132 25141 25203 25214 25222 25231 25302 25312 25321 30234 30243 30252
30324 30333 30340 30342 30414 30423 30430 30432 31011 31235 31244 31253
31325 31334 31340 31343 31405 31415 31424 31432 31441 31504 31521 32025
32034 32100 32144 32152 32225 32234 32240 32243 32251 32304 32315 32324
32330 32333 32342 32403 32414 32423 32512 33024 33031 33033 33125 33134
33140 33143 33151 33215 33224 33230 33233 33242 33303 33314 33320 33323
33332 33412 33431 34124 34133 34203 34214 34223 34232 34241 34310 34313
34322 34411 35202 35213 35221 35311 40323 40332 40341 40431 40505 40513
41135 41144 41240 41243 41252 41324 41330 41333 41342 41403 41414 41423
41512 42033 42134 42143 42230 42233 42242 42303 42310 42314 42323 42332
42341 42413 42422 42431 43023 43124 43130 43133 43142 43203 43220 43223
43232 43241 43302 43313 43322 43331 43421 44114 44123 44132 44210 44213
44222 44231 44312 44321 50413 50422 50504 51233 51242 51251 51323 51332
51341 51413 51422 52023 52133 52142 52151 52223 52232 52241 52313 52322
52331 52421 53102 53114 53122 53210 53213 53321 54201 54212 54221 54311