89.格雷编码.js

/*
 * @lc app=leetcode.cn id=89 lang=javascript
 *
 * [89] 格雷编码
 */

// @lc code=start
/**
 * @param {number} n
 * @return {number[]}
 */
var grayCode = function (n) {
	let map = [];
	for (let index = 1; index < Math.pow(2, n); index++) {
		map.push(index);
	}

	function unit(last, remains) {
		for (let index = 0; index < remains.length; index++) {
			let remain = remains[index];
			if (Number.isInteger(Math.log2(remain ^ last))) {
				if (remain.length === 1) {
					return [remain];
				} else {
					return [
						remain,
						...(unit(
							remain,
							remains.slice(0, index).concat(remains.slice(index + 1))
						) || []),
					];
				}
			} else {
				// console.log(remains[index]);
			}
		}
	}
	return [0, ...unit(0, map)];

	/* 	let tasks = [[0]];
	while (tasks.length) {
		let tempTasks = [];
		for (let task of tasks) {
			if (task.length === Math.pow(2, n)) {
				return task;
			}
			let last = task[task.length - 1];
			map
				.filter((e) => {
					return !task.includes(e) && Number.isInteger(Math.log2(e ^ last));
				})
				.forEach((e) => {
					tempTasks.push([...task, e]);
				});
		}
		tasks = tempTasks;
	}
	return []; */
};
// @lc code=end
console.log(JSON.stringify(isGray(grayCode(10))));
console.log(
	JSON.stringify(
		isGray([
			0,
			1,
			3,
			2,
			6,
			7,
			5,
			4,
			12,
			13,
			15,
			14,
			10,
			11,
			9,
			8,
			24,
			25,
			27,
			26,
			30,
			31,
			29,
			28,
			20,
			21,
			23,
			22,
			18,
			19,
			17,
			16,
			48,
			49,
			51,
			50,
			54,
			55,
			53,
			52,
			60,
			61,
			63,
			62,
			58,
			59,
			57,
			56,
			40,
			41,
			43,
			42,
			46,
			47,
			45,
			44,
			36,
			37,
			39,
			38,
			34,
			35,
			33,
			32,
			96,
			97,
			99,
			98,
			102,
			103,
			101,
			100,
			108,
			109,
			111,
			110,
			106,
			107,
			105,
			104,
			120,
			121,
			123,
			122,
			126,
			127,
			125,
			124,
			116,
			117,
			119,
			118,
			114,
			115,
			113,
			112,
			80,
			81,
			83,
			82,
			86,
			87,
			85,
			84,
			92,
			93,
			95,
			94,
			90,
			91,
			89,
			88,
			72,
			73,
			75,
			74,
			78,
			79,
			77,
			76,
			68,
			69,
			71,
			70,
			66,
			67,
			65,
			64,
			192,
			193,
			195,
			194,
			198,
			199,
			197,
			196,
			204,
			205,
			207,
			206,
			202,
			203,
			201,
			200,
			216,
			217,
			219,
			218,
			222,
			223,
			221,
			220,
			212,
			213,
			215,
			214,
			210,
			211,
			209,
			208,
			240,
			241,
			243,
			242,
			246,
			247,
			245,
			244,
			252,
			253,
			255,
			254,
			250,
			251,
			249,
			248,
			232,
			233,
			235,
			234,
			238,
			239,
			237,
			236,
			228,
			229,
			231,
			230,
			226,
			227,
			225,
			224,
			160,
			161,
			163,
			162,
			166,
			167,
			165,
			164,
			172,
			173,
			175,
			174,
			170,
			171,
			169,
			168,
			184,
			185,
			187,
			186,
			190,
			191,
			189,
			188,
			180,
			181,
			183,
			182,
			178,
			179,
			177,
			176,
			144,
			145,
			147,
			146,
			150,
			151,
			149,
			148,
			156,
			157,
			159,
			158,
			154,
			155,
			153,
			152,
			136,
			137,
			139,
			138,
			142,
			143,
			141,
			140,
			132,
			133,
			135,
			134,
			130,
			131,
			129,
			128,
			384,
			385,
			387,
			386,
			390,
			391,
			389,
			388,
			396,
			397,
			399,
			398,
			394,
			395,
			393,
			392,
			408,
			409,
			411,
			410,
			414,
			415,
			413,
			412,
			404,
			405,
			407,
			406,
			402,
			403,
			401,
			400,
			432,
			433,
			435,
			434,
			438,
			439,
			437,
			436,
			444,
			445,
			447,
			446,
			442,
			443,
			441,
			440,
			424,
			425,
			427,
			426,
			430,
			431,
			429,
			428,
			420,
			421,
			423,
			422,
			418,
			419,
			417,
			416,
			480,
			481,
			483,
			482,
			486,
			487,
			485,
			484,
			492,
			493,
			495,
			494,
			490,
			491,
			489,
			488,
			504,
			505,
			507,
			506,
			510,
			511,
			509,
			508,
			500,
			501,
			503,
			502,
			498,
			499,
			497,
			496,
			464,
			465,
			467,
			466,
			470,
			471,
			469,
			468,
			476,
			477,
			479,
			478,
			474,
			475,
			473,
			472,
			456,
			457,
			459,
			458,
			462,
			463,
			461,
			460,
			452,
			453,
			455,
			454,
			450,
			451,
			449,
			448,
			320,
			321,
			323,
			322,
			326,
			327,
			325,
			324,
			332,
			333,
			335,
			334,
			330,
			331,
			329,
			328,
			344,
			345,
			347,
			346,
			350,
			351,
			349,
			348,
			340,
			341,
			343,
			342,
			338,
			339,
			337,
			336,
			368,
			369,
			371,
			370,
			374,
			375,
			373,
			372,
			380,
			381,
			383,
			382,
			378,
			379,
			377,
			376,
			360,
			361,
			363,
			362,
			366,
			367,
			365,
			364,
			356,
			357,
			359,
			358,
			354,
			355,
			353,
			352,
			288,
			289,
			291,
			290,
			294,
			295,
			293,
			292,
			300,
			301,
			303,
			302,
			298,
			299,
			297,
			296,
			312,
			313,
			315,
			314,
			318,
			319,
			317,
			316,
			308,
			309,
			311,
			310,
			306,
			307,
			305,
			304,
			272,
			273,
			275,
			274,
			278,
			279,
			277,
			276,
			284,
			285,
			287,
			286,
			282,
			283,
			281,
			280,
			264,
			265,
			267,
			266,
			270,
			271,
			269,
			268,
			260,
			261,
			263,
			262,
			258,
			259,
			257,
			256,
			768,
			769,
			771,
			770,
			774,
			775,
			773,
			772,
			780,
			781,
			783,
			782,
			778,
			779,
			777,
			776,
			792,
			793,
			795,
			794,
			798,
			799,
			797,
			796,
			788,
			789,
			791,
			790,
			786,
			787,
			785,
			784,
			816,
			817,
			819,
			818,
			822,
			823,
			821,
			820,
			828,
			829,
			831,
			830,
			826,
			827,
			825,
			824,
			808,
			809,
			811,
			810,
			814,
			815,
			813,
			812,
			804,
			805,
			807,
			806,
			802,
			803,
			801,
			800,
			864,
			865,
			867,
			866,
			870,
			871,
			869,
			868,
			876,
			877,
			879,
			878,
			874,
			875,
			873,
			872,
			888,
			889,
			891,
			890,
			894,
			895,
			893,
			892,
			884,
			885,
			887,
			886,
			882,
			883,
			881,
			880,
			848,
			849,
			851,
			850,
			854,
			855,
			853,
			852,
			860,
			861,
			863,
			862,
			858,
			859,
			857,
			856,
			840,
			841,
			843,
			842,
			846,
			847,
			845,
			844,
			836,
			837,
			839,
			838,
			834,
			835,
			833,
			832,
			960,
			961,
			963,
			962,
			966,
			967,
			965,
			964,
			972,
			973,
			975,
			974,
			970,
			971,
			969,
			968,
			984,
			985,
			987,
			986,
			990,
			991,
			989,
			988,
			980,
			981,
			983,
			982,
			978,
			979,
			977,
			976,
			1008,
			1009,
			1011,
			1010,
			1014,
			1015,
			1013,
			1012,
			1020,
			1021,
			1023,
			1022,
			1018,
			1019,
			1017,
			1016,
			1000,
			1001,
			1003,
			1002,
			1006,
			1007,
			1005,
			1004,
			996,
			997,
			999,
			998,
			994,
			995,
			993,
			992,
			928,
			929,
			931,
			930,
			934,
			935,
			933,
			932,
			940,
			941,
			943,
			942,
			938,
			939,
			937,
			936,
			952,
			953,
			955,
			954,
			958,
			959,
			957,
			956,
			948,
			949,
			951,
			950,
			946,
			947,
			945,
			944,
			912,
			913,
			915,
			914,
			918,
			919,
			917,
			916,
			924,
			925,
			927,
			926,
			922,
			923,
			921,
			920,
			904,
			905,
			907,
			906,
			910,
			911,
			909,
			908,
			900,
			901,
			903,
			902,
			898,
			899,
			897,
			896,
			640,
			641,
			643,
			642,
			646,
			647,
			645,
			644,
			652,
			653,
			655,
			654,
			650,
			651,
			649,
			648,
			664,
			665,
			667,
			666,
			670,
			671,
			669,
			668,
			660,
			661,
			663,
			662,
			658,
			659,
			657,
			656,
			688,
			689,
			691,
			690,
			694,
			695,
			693,
			692,
			700,
			701,
			703,
			702,
			698,
			699,
			697,
			696,
			680,
			681,
			683,
			682,
			686,
			687,
			685,
			684,
			676,
			677,
			679,
			678,
			674,
			675,
			673,
			672,
			736,
			737,
			739,
			738,
			742,
			743,
			741,
			740,
			748,
			749,
			751,
			750,
			746,
			747,
			745,
			744,
			760,
			761,
			763,
			762,
			766,
			767,
			765,
			764,
			756,
			757,
			759,
			758,
			754,
			755,
			753,
			752,
			720,
			721,
			723,
			722,
			726,
			727,
			725,
			724,
			732,
			733,
			735,
			734,
			730,
			731,
			729,
			728,
			712,
			713,
			715,
			714,
			718,
			719,
			717,
			716,
			708,
			709,
			711,
			710,
			706,
			707,
			705,
			704,
			576,
			577,
			579,
			578,
			582,
			583,
			581,
			580,
			588,
			589,
			591,
			590,
			586,
			587,
			585,
			584,
			600,
			601,
			603,
			602,
			606,
			607,
			605,
			604,
			596,
			597,
			599,
			598,
			594,
			595,
			593,
			592,
			624,
			625,
			627,
			626,
			630,
			631,
			629,
			628,
			636,
			637,
			639,
			638,
			634,
			635,
			633,
			632,
			616,
			617,
			619,
			618,
			622,
			623,
			621,
			620,
			612,
			613,
			615,
			614,
			610,
			611,
			609,
			608,
			544,
			545,
			547,
			546,
			550,
			551,
			549,
			548,
			556,
			557,
			559,
			558,
			554,
			555,
			553,
			552,
			568,
			569,
			571,
			570,
			574,
			575,
			573,
			572,
			564,
			565,
			567,
			566,
			562,
			563,
			561,
			560,
			528,
			529,
			531,
			530,
			534,
			535,
			533,
			532,
			540,
			541,
			543,
			542,
			538,
			539,
			537,
			536,
			520,
			521,
			523,
			522,
			526,
			527,
			525,
			524,
			516,
			517,
			519,
			518,
			514,
			515,
			513,
			512,
		])
	)
);
function isGray(arr) {
	for (let index = 0; index < arr.length - 1; index++) {
		if (!Number.isInteger(Math.log2(arr[index] ^ arr[index + 1]))) {
			return false;
		}
	}
	return true;
}